Big O Domanda su un algoritmo con (n ^ 2 + n) / 2 tasso di crescita

Quando si calcola la complessità Big-O di un algoritmo, la cosa che viene mostrata è il fattore che dà il maggior contributo all'aumento del tempo di esecuzione se aumenta il numero di elementi su cui si esegue l'algoritmo.

Se hai un algoritmo con una complessità di (n^2 + n)/2 e raddoppi il numero di elementi, allora la costante 2 non influenza l'aumento del tempo di esecuzione, il termine n causa un raddoppiamento nell'esecuzione tempo e il termine n^2 provoca un aumento di quattro volte del tempo di esecuzione.
Poiché il termine n^2 ha il maggior contributo, la complessità di Big-O è O(n^2) .

La definizione è quella

f(n) = O(g(n))

se esiste qualche costante C > 0 tale che, per tutti n maggiore di alcuni n_0, abbiamo

|f(n)| <= C * |g(n)|

Questo è chiaramente vero per f (n) = n ^ 2 eg (n) = 1/2 n ^ 2, dove la costante C dovrebbe essere 2. È anche facile vedere che è vero per f (n) = n ^ 2 eg (n) = 1/2 (n ^ 2 + n).

Quando parli di complessità, ti interessano solo le variazioni del fattore tempo in base al numero di elementi ( n ).

Come tale puoi rimuovere qualsiasi fattore costante (come 2 qui).

Questo ti lascia con O(n^2 + n) .

Ora, per un ragionevole% di% in abbondanza il prodotto, ovvero n , sarà significativamente più grande di solo n * n , che è il motivo per cui puoi saltare anche quella parte, il che ti lascia davvero con una complessità finale di n .

È vero, per i piccoli numeri ci sarà una differenza significativa, ma questo diventa più marginalmente maggiore diventa il tuo O(n^2) .

Non è così "(n² + n) / 2 si comporta come n² quando n è grande", è che (n² + n) / 2 cresce come n² < strong> come n aumenta .

Ad esempio, con n aumenta da 1.000 a 1.000.000

(n² + n) / 2  increases from  500500 to  500000500000
(n²) / 2      increases from  500000 to  500000000000
(n²)          increases from 1000000 to 1000000000000

Allo stesso modo, con n aumenta da 1.000.000 a 1.000.000.000

(n² + n) / 2  increases from  500000500000 to  500000000500000000
(n²) / 2      increases from  500000000000 to  500000000000000000
(n²)          increases from 1000000000000 to 1000000000000000000

Crescono allo stesso modo, che è ciò di cui parla Big O Notation.

Se trama (n² + n) / 2 e n² / 2 su Wolfram Alpha , sono così simili che sono difficili da distinguere per n = 100. Se tu stampa tutti e tre su Wolfram Alpha , vedi due righe separate da un fattore costante di 2.

Sembra proprio che tu debba elaborare un po 'di più la notazione big O . Com'è comoda questa notazione, è molto fuorviante a causa dell'uso di un segno di uguale, che non è usato qui per denotare l'uguaglianza delle funzioni.

Come sapete, questa notazione esprime un confronto asintotico di funzioni e scrivere f = O (g) significa che f (n) cresce al massimo alla velocità g (n) come n va all'infinito. Un modo semplice per tradurre questo è dire che la funzione f / g è limitata. Ma, naturalmente, dobbiamo occuparci dei luoghi in cui g è zero e ci ritroviamo con la definizione più robusta che puoi leggi quasi ovunque .

Questa notazione risulta molto comoda per l'informatica - è per questo che è così diffusa - ma dovrebbe essere gestita con attenzione poiché il segno di uguale che vediamo non indica un'eguaglianza di funzioni . Questo è come dire che 2 = 5 mod 3 non implica che 2 = 5 e se sei appassionato di algebra, puoi effettivamente capire la grande notazione O come un modulo di uguaglianza qualcosa.

Ora, per tornare alla tua domanda specifica, è del tutto inutile calcolare alcuni valori numerici e confrontarli: per quanto grande sia un milione, non tiene conto del comportamento asintotico. Sarebbe più utile tracciare il rapporto delle funzioni f (n) = n (n-1) / 2 e g (n) = n² - ma in questo caso speciale possiamo facilmente vedere che f (n) / g (n) è minore di 1/2 se n > 0 che implica che f = O (g) .

Per migliorare la tua comprensione della notazione, dovresti

• Lavora con una definizione pulita, non un'impressione fuzzy basata su le cose sono simili - come l'hai appena sperimentato, un'impressione così sfocata non funziona bene.

• Prenditi del tempo per elaborare esempi in dettaglio. Se risolvi un minimo di cinque esempi in una settimana, sarà sufficiente per migliorare la tua sicurezza. Questo è uno sforzo che vale sicuramente.

Nota algebrica Se A è l'algebra di tutte le funzioni Ν → Ν e C il subalgebra di funzioni limitate, data una funzione f l'insieme di funzioni appartenenti a O (f) è un C -submodule di A e le regole di calcolo sulla notazione O grande descrivono semplicemente come A funziona su questi sottomoduli. Quindi, l'uguaglianza che vediamo è un'eguaglianza di C -submoduli di A , questo è solo un altro tipo di modulo.

Penso che tu fraintenda cosa significhi la grande notazione O.

Quando vedi O (N ^ 2) significa fondamentalmente: quando il problema diventa 10 volte più grande, il tempo per risolverlo sarà: 10 ^ 2 = 100 volte più grande.

Diamo un pugno di 1000 e 10000 nella tua equazione: 1000: (1000 ^ 2 + 1000) / 2 = 500500 10000: (10000 ^ 2 + 10000) / 2 = 50005000

50005000/500500 = 99,91

Quindi, mentre la N è diventata 10 volte più grande, le soluzioni sono diventate 100 volte più grandi. Quindi si comporta: O (N ^ 2)

if n was a 1,000,000 then

(n^2 + n) / 2  =  500000500000  (5.00001E+11)
(n^2) / 2      =  500000000000  (5E+11)
(n^2)          = 1000000000000  (1E+12)

1000000000000.00 cosa?

Mentre la complessità ci offre un modo per prevedere un costo reale (secondi o byte a seconda che stiamo parlando di complessità temporale o complessità spaziale), non ci fornisce un numero di secondi, o qualsiasi altro particolare unità.

Ci dà un certo grado di proporzione.

Se un algoritmo deve fare qualcosa di n² volte, allora ci vorrà n² × c per un certo valore di c che è il tempo impiegato da ogni iterazione.

Se un algoritmo deve fare qualcosa di n² ÷ 2 volte, allora ci vorrà n² × c per un valore di c che è il doppio di ogni iterazione.

In entrambi i casi, il tempo impiegato è ancora proporzionale a n².

Ora, questi fattori costanti non sono qualcosa che possiamo semplicemente ignorare; in effetti si può avere il caso in cui un algoritmo con complessità O (n²) fa meglio di uno con O (n) complessità, perché se stiamo lavorando su un piccolo numero di elementi l'impatto dei fattori di consenso è maggiore e può sopraffare altre preoccupazioni . (Infatti, anche O (n!) È uguale a O (1) per valori sufficientemente bassi di n).

Ma non sono ciò di cui la complessità ci parla.

In pratica, ci sono alcuni modi in cui possiamo migliorare le prestazioni di un algoritmo:

1. Migliora l'efficienza di ogni iterazione: O (n²) gira ancora in n² × c secondi, ma c è più piccolo.
2. Riduci il numero di casi visti: O (n²) continua a essere eseguito in n² × c secondi, ma n è minore.
3. Sostituisci l'algoritmo con uno che ha gli stessi risultati, ma una complessità inferiore: es. se potessimo ripubblicare qualcosa O (n²) a qualcosa O (n log n) e quindi cambiare da n² × c₀ secondi a (n log n) × c₁ secondi.

O per guardarlo in un altro modo, abbiamo ottenuto f(n)×c secondi e puoi migliorare le prestazioni riducendo c , riducendo n o riducendo quale f restituisce per un dato n .

Il primo che possiamo fare con alcuni micro-opts all'interno di un loop, o usando un hardware migliore. Dà sempre un miglioramento.

Il secondo che possiamo fare, forse, identificando un caso in cui possiamo eseguire un cortocircuito dall'algoritmo prima che tutto venga esaminato, o filtrare alcuni dati che non saranno significativi. Non darà un miglioramento se il costo di ciò è superiore al guadagno, ma in generale sarà un miglioramento maggiore rispetto al primo caso, specialmente con un grande n.

Il terzo che possiamo fare utilizzando completamente un algoritmo diverso. Un classico esempio potrebbe sostituire un bubble sort con un quicksort. Con un basso numero di elementi potremmo aver peggiorato le cose (se c₁ è maggiore di c₀), ma generalmente consente i maggiori guadagni, specialmente con molto grandi n.

Nell'uso pratico, le misure di complessità ci permettono di ragionare sulle differenze tra algoritmi proprio perché ignorano la questione di come la riduzione di n o c aiuterà, a concentrarsi sull'esame di f()

Fattore costante

Il punto della notazione O grande è che puoi scegliere un fattore costante arbitrariamente grande in modo che O (funzione (n)) sia sempre più grande della funzione C * (n). Se l'algoritmo A è un miliardo di volte più lento dell'algoritmo B, allora hanno la stessa complessità O, purché tale differenza non cresca quando n cresce in modo arbitrario.

Assumiamo un fattore costante di 1000000 per illustrare il concetto: è un milione di volte più grande del necessario, ma questo dimostra che sono considerati irrilevanti.

(n ^ 2 + n) / 2 "si adatta a" O (n ^ 2) perché per ogni n, non importa quanto grande, (n ^ 2 + n) / 2 < 1000000 * n ^ 2.

(n ^ 2 + n) / 2 "non si adatta" a un set più piccolo, ad es. O (n) perché per alcuni valori (n ^ 2 + n) / 2 > 1000000 * n.

I fattori costanti possono essere arbitrariamente grandi: un algoritmo con tempo di esecuzione di n anni ha complessità O (n) che è "migliore" di un algoritmo con un tempo di esecuzione di n * log (n) microsecondi.

Big-O si basa su "quanto sia complicato" un algoritmo. Se hai due algoritmi e uno richiede n^2*k secondi per essere eseguito, l'altro richiede n^2*j secondi per essere eseguito, quindi puoi discutere su quale sia il migliore e potresti essere in grado di fare alcune interessanti ottimizzazioni per provare a influenza k o j , ma entrambi questi algoritmi sono lenti rispetto a un algoritmo che richiede n*m per essere eseguito. Non importa quanto piccolo tu faccia le costanti k o j , per un input abbastanza grande l'algoritmo n*m vincerà sempre, anche se m è abbastanza grande.

Quindi chiamiamo i primi due algoritmi O(n^2) , e chiamiamo il secondo O(n) . Divide piacevolmente il mondo in classi di algoritmi. Questo è ciò che Big-O è tutto. È come dividere i veicoli in auto, camion e autobus, ecc. C'è molta differenza tra le macchine, e puoi passare tutto il giorno a discutere se una Prius è meglio di una Chevy Volt, ma alla fine se tu è necessario mettere 12 persone in una, quindi questo è un argomento piuttosto insensato. :)