L'analisi dell'ordinamento per inserzione non è uguale a O (n ^ 2)?

Question

L'analisi dell'ordinamento per inserzione non è uguale a O (n ^ 2)?

#1 da (6 voti)
#2 da (1 voti)
#3 da (1 voti)

1

Sto imparando di più su algoritmi e strutture dati.

Secondo Wikipedia e altre fonti affidabili, un ordinamento di inserimento ha una complessità temporale di caso peggiore di O (n < sup> 2 ). Sto provando a misurare quella complessità nel codice:

def swap(n, i, j):
    first, second = n[i], n[j]

    n[i] = second
    n[j] = first

def insertion_sort(n):
    size, steps = len(n), 0

    for i in range(1, len(n)):
        j = i
        steps += 1
        while j > 0 and n[j - 1] > n[j]:
            swap(n, j - 1, j)
            steps += 1
            j = j - 1

    return size, steps

print "size: %d, steps: %d" % insertion_sort([i for i in xrange(1000-1, -1, -1)])

Above è Python, un semplice metodo di scambio per scambiare valori a determinati indici e un semplice algoritmo di ordinamento di inserimento che contiene anche un conteggio del numero di iterazioni / operazioni eseguite.

La linea finale crea un array che assomiglia a [999, 998, ... 0] , 1000 elementi nel peggiore ordine di classificazione: inverso.

Quando eseguo questo codice, vedo che per l'array di lunghezza 1000 ho eseguito 500499 passaggi per ordinarlo correttamente.

Ovviamente sto facendo qualcosa di sbagliato qui. Perché non vedo 1000 iterazioni ² (100000) richieste, se si tratta del comportamento peggiore previsto?

algorithms sorting

posta Naftuli Kay 07.08.2015 - 03:17

fonte

3 risposte

Leggi altre domande sui tag algorithms sorting

Funzioni di test dell'unità che chiamano altre funzioni testate [duplicate] Una proprietà privata è uguale a un campo pubblico?

score 6 · Answer 1

Poiché il risultato del tuo codice (fisso) ti confonde ancora, cerco di rispondere alla tua domanda:

La notazione O non è una notazione esatta della formula. Solo perché qualcosa è O (1) non significa che richiede un solo passo, solo perché è O (n²) non significa che richiede n² passi. L'O-Notation è un modo astratto per definire quanto sia complesso un algoritmo. Certo, non hai il tuo 1000² per il tuo O (n²) con n = 1000, ma era previsto. Lì non è O (n² / 2 più alcuni).

Il tuo algoritmo deve scorrere su ogni singolo elemento e per ogni singolo elemento, ha bisogno di ripetere su una parte di elementi, che è essenzialmente una complessità quadratica, quindi O (n²)

Vedi qui per un elenco di possibili (o meglio, comunemente usate) O-notazioni.

score 1 · Answer 2

1

O (n ²) significa che se aumenti n da 1000 a 10000 il numero di operazioni sarà intorno a 10 ² = 100 volte più grande (nel tuo caso di circa 50.000.000 di operazioni).

risposta data 07.08.2015 - 04:58

fonte

score 1 · Answer 3

In questa formula O, il valore temporale è raramente 1. Ancora più importante, perché il valore temporale può essere diverso per diversi algoritmi. Un algoritmo che scala linearmente, O (n), può essere significativamente più lento di un algoritmo che scala in modo quadratico, O (n ²).

Conoscere i valori temporali relativi alla notazione O grande per diversi algoritmi e dimensioni attese di n può aiutare a scegliere l'algoritmo appropriato. Per un piccolo set un algoritmo veloce che scala in modo non lineare può essere più veloce di un algoritmo alternativo che scala linearmente. Se l'insieme sarà sempre piccolo, allora l'algoritmo con il valore temporale più piccolo potrebbe essere una scelta migliore. Un algoritmo con un valore temporale maggiore può essere una scelta migliore se il set sarà sempre grande. Alcuni test possono essere necessari per determinare la dimensione di pareggio. Se le dimensioni possono variare, la scelta dell'algoritmo potrebbe essere più difficile.

Inoltre, gli algoritmi che scalano in modo più lineare possono essere più complessi di algoritmi che scalano in modo meno lineare. La maggiore complessità potrebbe aumentare i costi e il numero di errori. Questo può influire sulla scelta dell'algoritmo.

Considera l'ordinamento

L'implementazione di bubble bubble più semplice ha una complessità di O (n ²). Tuttavia è semplice e veloce per piccoli set.
Un ordinamento di bolle comuni può essere facilmente ottimizzato decrementando la dimensione del ciclo esterno di 1 ogni iterazione che richiede metà dei confronti al costo di un ciclo esterno leggermente più lento. Ciò può ridurre il valore temporale O a quasi la metà di quello dell'implementazione della bolla più semplice. Ha ancora una complessità di O (n ²).
Il tracciamento in cui sono state eseguite le mosse può eliminare la complessità di un ordinamento di bolle in O (n) per l'input ordinato, ma aumenta il valore temporale.
L'ordinamento heap ha una complessità di O (n log n) a seconda del set di input. Tuttavia, il valore temporale è significativamente più alto di quello di un bubble sort. Per il piccolo n sarà più lento e sarà più complesso da implementare.
Gli altri algoritmi di ordinamento hanno valori temporali e scala differenti. Anche la complessità di implementazione varia.