Perché bubble sort O (n^2)?

Question

int currentMinIndex = 0; 

for (int front = 0; front < intArray.length; front++) 
{ 
    currentMinIndex = front; 

    for (int i = front; i < intArray.length; i++) 
    { 
     if (intArray[i] < intArray[currentMinIndex]) 
     { 
      currentMinIndex = i; 
     } 
    } 

    int tmp = intArray[front]; 
    intArray[front] = intArray[currentMinIndex]; 
    intArray[currentMinIndex] = tmp; 
} 

Il ciclo interno sta iterando: n + (n-1) + (n-2) + (n-3) + ... + 1 volte.

Il ciclo esterno sta iterando: n volte.

in modo da ottenere n * (la somma dei numeri da 1 a n)

non è che n * (n * (n + 1)/2) = n * ((n^2) + n/2)

Quale sarebbe (n^3) + (n^2)/2 = O (n^3)?

Sono positivo, sto sbagliando. Perché non è O (n^3)?

Answer 1

Sei corretto che il ciclo esterno itera su n volte e il ciclo interno itera anche n volte, ma stai contando due volte il lavoro. Se si conta il totale del lavoro svolto sommando il lavoro svolto per ogni iterazione del ciclo di primo livello si ottiene che la prima iterazione non funziona, la seconda n - 1, la terza n - 2, ecc., Dal momento che l'ith l'iterazione del ciclo di livello superiore ha il ciclo interno che esegue il lavoro n - i.

In alternativa, è possibile eseguire il conteggio del lavoro svolto moltiplicando la quantità di lavoro eseguita dal ciclo interno per il numero totale di volte in cui il ciclo viene eseguito. Il ciclo interno esegue O (n) su ogni iterazione e il ciclo esterno esegue le iterazioni O (n), quindi il lavoro totale è O (n).

Si sta commettendo un errore cercando di combinare queste due strategie. È vero che il ciclo esterno non funziona la prima volta, quindi n - 1, quindi n - 2, ecc. Tuttavia, non si moltiplica questo lavoro per n per ottenere il totale. Questo conterebbe ogni iterazione n volte. Invece, puoi semplicemente sommarli insieme.

Spero che questo aiuti!

Answer 2

I itera anello interno di n volte (nel caso peggiore):

for(int i = front; i < intArray.length; i++) 

itera ciclo esterno n volte:

for(int front = 0; front < intArray.length; front++) 

Pertanto O (n^2)

Answer 3

tuo interno loop iterating, IN TOTAL, come hai detto n + (n-1) + (n-2) + (n-3) + ... + 1 volte. Quindi è O (n + (n-1) + (n-2) + (n-3) + ... + 1) = O (n (n + 1)/2) = O (n^2)

Answer 4

Come è fondamentalmente calcolare N ...

• Ogni riga: 1

• Ogni loop * N

  numeri Così si inizia ad aggiungere arrivare al tuo primo loop ora avete N + 1, vai avanti e alla fine ottieni N * N o N^2 per il tempo più un certo numero. Tirando fuori il numero come è generalmente insignificante rispetto a N.

Praticamente N è una rappresentazione di tutti gli elementi del tipo ad anello di come 1,2,3 ... N. Quindi rappresenta semplicemente un numero non quante volte un loop, loop.

Answer 5

Solo per il gusto di avere una versione Python di bubble sort ...

def bubble_sort(input): 
    n = len(input) 
    iterations = 0 
    for i in xrange(n, 1, -1): 
     for j in range(0, i - 1): 
      iterations += 1 
      if input[j] > input[j+1]: 
       input[j],input[j+1] = input[j+1],input[j] 

    print iterations 
    return input 

Le iterazioni sono state aggiunte al ciclo interno per contare le iterazioni totali. Niente a che fare con il bubble sort.

Passando un array di 5 elementi, il risultato è 15 iterazioni non 25. Anche quando pre-ordinato, risulta anche in 15 iterazioni. Ma la complessità deve anche tener conto del confronto e dello scambio.

Answer 6

k=1(sigma k)n = n(n+1)/2 
because: 
    s = 1 + 2 + ... + (n-1) + n 
    s = n + (n-1) + ... + 2  + 1 
+) 
=================================== 
    2s = n*(n+1) 
    s = n(n+1)/2 
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1 
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n 
therefore, n(n+1)/2 - n = n(n-1)/2 
which is 1/2(n^2-n) => O(1/2(n^2-n)) 
in big O notation, we remove constant, so 
O(n^2-n) 
n^2 is larger than n 
O(n^2)