Tempo di esecuzione dell'algoritmo di ordinamento a bolle specificato

Question

Tempo di esecuzione dell'algoritmo di ordinamento a bolle specificato

#1 da (1 voti)

2

Ho lavorato su alcune domande sugli algoritmi negli ultimi giorni e un problema di ordinamento delle bolle in particolare mi ha dato grattacapi.

for (k=1; k <= A.length - 1; k++) {         //Line 1
   for (m=1; m <= A.length - k; m++) {      //Line 2
      if (A[m-1] > A[m]) {                  //Line 3
        Swap (A[m-1], A[m]);                //Line 4
}

Ora, dovrei trovare il tempo di esecuzione di questo algoritmo nello scenario peggiore, e so che è O (n ^ 2), ma il problema che sto avendo è scoprire quante volte è ogni linea eseguito.

Ad esempio, la linea 1 richiederà n unità di tempo, mentre la linea 4 dipende dalla complessità della funzione Swap. Tuttavia, la linea 2 d'altra parte prenderà [(n-1) * ? ] unità di tempo (ho provato a scoprire esattamente e ho ottenuto (n-1) * n) e sono calpestato nel trovare come eseguire l'istruzione IF, ma presumo che occorrerà (? - 1 ) volte. Se qualcuno potesse darmi una spiegazione su come farlo, lo apprezzerei molto.

algorithms sorting algorithm-analysis

posta LazyTarinaX 19.10.2015 - 01:22

fonte

1 risposta

Leggi altre domande sui tag algorithms sorting algorithm-analysis

Controller di grandi dimensioni in Web API ASP.NET, Come organizzare Feed std :: streambuf per Non-blocking std :: istream Leggi

score 1 · Answer 1

Non preoccuparti dell'istruzione if. Se i tuoi dati sono casuali, puoi supporre che l'istruzione if sarà true circa la metà del tempo, ma non devi preoccupartene. La regola generale di base per questo tipo di analisi è molto semplice: cicli di conteggio . Quando si tratta di ciò che determina il tempo di esecuzione dell'algoritmo è quante volte viene eseguita l'istruzione if nella sua interezza.

Ecco perché big-O è espresso come un asintoto. Si hanno 2 cicli annidati e con l'aumentare della dimensione del set di dati, il tempo di esecuzione totale viene pesato sempre più sul quadrato della dimensione, quindi la complessità temporale è nell'ordine di n ^ 2. Per visualizzare questo, ricorda che statisticamente, ti aspetti che l'affermazione if sia vera metà del tempo. Prova a tracciare 0.5(x^2) e quindi traccia (x^2) , e scopri come il ridimensionamento 1/2 diventa sempre meno importante man mano che x cresce sempre più grande.