Durata (grande O)) di un algoritmo

Question

sto calcolando il tempo di esecuzione per questo algoritmo?

       Cost  No Of Times 

for(j=1;j<=n-1;j++){   c1  n(loop will run for n-1 times +1 for failed cond    

    for(i=0;i<=n-2;i++){  c2  n*(n-1) (n-1 from outer loop and n for inner 

     if(a[i]>a[i+1]){  c3  (n-1)*(n-1) 

      Swap    c4  (n-1)*(n-1) {in worst case } 
     } 
    } 

nel caso peggiore T (n) = c1 * n + c2 * (n-1) n + c3 (n-1) (n-1) + c4 * (n- 1) (n-1) che è O (n^2)

In caso migliore:

T (n) = c1 * n + c2 * (n-1) n + c3 (n-1) (n-1) che è O (n^2).

MA in realtà nel migliore dei casi bubble sort ha complessità temporale O (n). Qualcuno può spiegare?

Answer 1

Bubble Sort ha O (n) complessità temporale nel migliore dei casi perché è possibile passare ad esso una lista già ordinata.

È necessario verificare se sono stati scambiati dopo il secondo ciclo annidato. Se non sono stati effettuati swap, l'elenco viene ordinato e non è necessario continuare, quindi è possibile interrompere il ciclo.

Per un elenco già ordinato, in questo caso avresti ripetuto tutti gli n elementi.

Answer 2

tuo algo per l'attuazione di bubble sort è corretto, ma non è efficiente,

// n è il numero totale di elments

do{ 

    swp = false // swp checks whether or not any variable has been swapped 
         in the inner loop 

     for(i=0;i<=n-2;i++){ 

        if(a[i]>a[i+1]) 

        { 
         swap(a[i],a[i+1]) 

         sw = true 
        } 
     n = n-1    
    }while(sw == true && n>0) 

SWP è una variabile che verifica se v'è stata alcuna swap nel anello interno o no,
se non ci sono stati scambi significa che il nostro array è ordinato.

Il caso migliore per bubblesort è quando gli elementi sono già in ordine crescente (in questo caso)
per cui il ciclo interno viene eseguito solo una volta, ma la condizione if (nel ciclo interno) non è mai soddisfatto e swp rimane falso e quindi usciamo dal ciclo esterno dopo una iterazione che dà complessità O (n) a bolle.

Answer 3

È possibile calcolare il numero di iterazioni (ciò che è all'interno del ciclo è irrilevante perché è tempo costante) utilizzando Sigma notazione:

Bubble Sort con un caso migliore tempo di esecuzione è in realtà una versione migliorata di questo algoritmo di ordinamento.

Nel primo parse (anello esterno), se è stato eseguito alcun scambio, cioè un'informazione decisivo che l'array è ordinato, ed è inutile per coprire tutti i casi.

Pertanto, il ciclo esterno potrebbe iterare una volta, e il ciclo interno sarebbe iterare n volte: questo è n + 1 iterazioni complessiva ==>O (n).