Come contare il confronto di ordinamento

Question

Come contare il confronto di ordinamento

#1 da (3 voti)

1

Quando si dice che questo tipo ha un numero M di confronti, che cosa significa?

Ad esempio:

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       if A[i-1] > A[i] then
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Ha

for i = 1 to n-1

o

for(int i = 0 ; i < n-1; i++)

questo confronto ( i < n-1 ) è stato preso in considerazione?

O nell'unione di tipo, accanto al confronto principale:

        if (v[first1]<v[first2])

alla fine di una funzione usata è scritto:

    while (first1 <= last1)
        temp[index++] = v[first1++];
    while (first2 <= last2)
        temp[index++] = v[first2++];
    for (index = first; index <= last; index++)
        v[index] = temp[index];

Questi confronti sono presi in considerazione?

algorithms sorting measurement

posta zahmati 24.04.2015 - 01:23

fonte

1 risposta

Leggi altre domande sui tag algorithms sorting measurement

Sembrerebbe poco professionale chiedere agli utenti di un'app mobile di disinstallare l'app e installarla di nuovo (installazione pulita)? [chiuso] La destinazione dei messaggi cout in un programma GUI

score 3 · Accepted Answer

Quando trovi una dichiarazione come "Numero M di confronti" sugli algoritmi di ordinamento in letteratura, l'autore indica in genere il numero di confronti tra gli elementi ordinati , non i confronti di qualcosa come gli indici di loop. Quindi, se ti viene chiesto questo in un incarico universitario, indovinerei che questo è il numero che si intende (ma per chiarire, se tu dai una risposta, perché non aggiungi una nota che descrive esattamente ciò che hai contato ).

In realtà, ciò presuppone che le operazioni predominanti in un algoritmo di ordinamento siano confronti e "swap" e che non ci siano più iterazioni del ciclo rispetto ai confronti tra gli elementi ordinati. Quando si assume quest'ultimo, per il calcolo di Big-O è irrilevante se si contano i "confronti dell'indice del ciclo" o meno.

Inoltre, si noti che un termine come "numero esatto di confronti" invece di "O (numero di confronti)" ha senso solo per un'implementazione specifica di un algoritmo, non "per un algoritmo" in generale. Quindi quando provi a confrontare il numero di confronti di la tua implementazione di bubble sort con un'implementazione diversa da un altro autore, devi assicurarti di non confrontare mele e arance. Questo è il motivo per cui i confronti in termini di "Big-O" hanno più senso quando si confrontano algoritmi a livello teorico.

Tuttavia, da un punto di vista più pratico, il conteggio dell'esatto "numero di confronti" (o swap) avrà davvero senso quando si tratta di confrontare rapidamente specifiche implementazioni di ordinamento su dati reali.