Come si fa a sapere che la notazione di analisi della complessità tempo da usare?

Question

Nella maggior parte delle classi introduttive algoritmo, vengono introdotti notazioni come $ O $ (Big O) e $ \ Theta $, e uno studente tipicamente imparare ad usare uno di questi per trovare la complessità temporale.

Tuttavia, ci sono altre notazioni, come $ o $, $ \ Omega $ e $ \ omega $. Ci sono scenari specifici in cui uno notazione sarebbe preferibile ad un altro?

Answer 1

Si riferisce alla Landau notazione . Essi non sono simboli diversi per la stessa cosa, ma hanno significati completamente diversi. Quale è "preferibile" dipende interamente sul conto desiderato.

$ f \ in \ cal {} O (g) $ significa che $ f $ cresce al massimo il più velocemente $ G $, asintoticamente e fino a un fattore costante; pensare ad esso come un $ \ leq $. $ F \ in O (g) $ è la forma più rigorosa, cioè $ <$.

$ f \ in \ Omega (g) $ ha il significato simmetrica: $ f $ cresce almeno velocemente da $ g $. $ \ Omega $ è il suo cugino più severe. Si può vedere che $ f \ in \ Omega (g) $ è equivalente a $ g \ in \ cal {} O (f) $.

$ f \ in \ Theta (g) $ significa che $ f $ cresce circa veloce da $ g $; formalmente $ f \ in \ cal {} O (g) \ cap \ Omega (g) $. $ F \ sim g $ (uguaglianza asintotica) è la forma più forte. Spesso $ media \ Theta $ Quando usiamo $ \ cal {O} $.

Si noti come $ \ cal {} O (g) $ ed i suoi fratelli sono classi di funzione . E 'importante essere molto consapevoli di questo e loro definizioni precise - che possono differire a seconda di chi sta parlando - quando si fa "aritmetica" con loro.

Quando dimostrando le cose, aver cura di lavoro con la vostra definizione precisa. Ci sono molte definizioni per i simboli di Landau in tutto (tutti con la stessa intuizione di base), alcuni dei quali sono equivalenti su alcuni set su funzioni, ma non su altri.

Lettura consigliata:

• Quali sono le regole per segni di uguaglianza con O-grande e poco-o?
• funzioni Ricerca per la crescita asintotica
• Come O e O riguardano peggiore e migliore dei casi?
• Nested Big notazione O
• di $ \ Theta $ per le funzioni negative
• Qual è il significato di O (m + n) $ $?
  è O (mn) considerata la crescita "quadratica" "lineare" o
• dei termini Landau Revisited
• Cosa fa grande O media come un termine di un rapporto di approssimazione?
• Qualsiasi altra domanda circa asintotica e Landau notazione come esercizio.

Se siete interessati ad utilizzare la notazione Landau in modo rigoroso e il suono, si può essere interessati a recente lavoro di Rutanen et al. [1]. Essi formulano criteri necessari e sufficienti per la notazione asintotica come li usiamo in algoritmica, mostrano che la definizione comune non soddisfa loro e fornire una (la, appunto) definizione funzionale.

---

1. Una definizione generale della notazione O per l'analisi algoritmo da K. Rutanen et al. (2015)

Answer 2

Big O: limite superiore

“Big O” ($ O $) è di gran lunga la più comune. Quando si analizza la complessità di un algoritmo, il più delle volte, ciò che conta è avere qualche limite superiore quanto velocemente il Tempo di stampa della corsa aumenta quando la dimensione dell'input cresce. In sostanza vogliamo sapere che l'esecuzione l'algoritmo non è andare a prendere “troppo a lungo”. Non possiamo esprimere questo in unità di tempo reali (secondi), perché ciò dipende dalla precisa applicazione (il modo in cui il programma è scritto, quanto è buono il compilatore è, quanto velocemente il processore della macchina è, ...). Quindi valutiamo ciò che non dipende da questi dettagli, che è quanto tempo ci vuole per eseguire l'algoritmo quando lo nutriamo grande ingresso. E abbiamo soprattutto attenzione quando possiamo essere sicuri che il programma è fatto, in modo che di solito vogliono sapere che ci vorrà così e tale quantità di tempo o meno.

Per dire che un algoritmo ha un tempo di esecuzione di $ O (f (n)) $ per una dimensione di ingresso $ n $ significa che esiste una costante $ K $ tale che il completamento del algoritmo al massimo in K \, $ f (n) $ fasi, vale a dire il tempo di esecuzione dell'algoritmo cresce più velocemente come $ f $ (fino a un fattore di scala). Notando $ T (n) $ il tempo di esecuzione dell'algoritmo per la dimensione di input $ n $, $ O (n) $ informalmente significa che $ T (n) \ le f (n) $ fino a qualche fattore di scala.

Limite inferiore

A volte, è utile avere più informazioni di un limite superiore. $ \ Omega $ è il contrario di $ O $: esprime che una funzione cresce almeno velocemente come un altro. $ T (n) = \ Omega (g (n)) $ significa che $ T (N) \ ge K 'g (n) $ per qualche costante $ K' $, o per dirla in modo informale, $ T (n) \ ge g (n) $ fino a qualche fattore di scala.

Quando il tempo di esecuzione dell'algoritmo può essere determinato con precisione, $ \ Theta $ combina $ O $ e $ \ Omega $: esprime che il tasso di crescita di una funzione è noto, fino ad un fattore di scala. $ T (n) = \ Theta (h (n)) $ significa che $ K h (n) \ ge T (n) \ ge K 'h (n) $ per alcune costanti di $ K $ e $ K' $. Informalmente parlando, $ T (n) \ circa h (n) $ fino a qualche fattore di scala.

Ulteriori considerazioni

Il “piccolo” $ O $ e $ \ omega $ sono usati molto meno spesso in analisi di complessità. Poco $ o $ è più forte di grande $ O $; dove $ O $ indica una crescita che non è più veloce, $ o $ indica che la crescita è strettamente più lenta. Al contrario, $ \ omega $ indica una crescita più rapida strettamente.

Sono stato un po 'informale, nella discussione di cui sopra. Wikipedia ha definizioni formall e un approccio più matematico.

Tenga presente che l'uso del segno uguale a $ T (n) = O (f (n)) $ e simili è un termine improprio. A rigor di termini, $ O (f (n)) $ è un insieme di funzioni della variabile $ n $, e dovremmo scrivere $ T \ O (f) $.

Esempio: alcuni algoritmi di ordinamento

Dato che questo è piuttosto asciutto, Vi faccio un esempio. La maggior parte degli algoritmi di ordinamento hanno un peggior caso il tempo di esecuzione quadratico, cioè un input di dimensione n $ $, il tempo di esecuzione dell'algoritmo è $ O (n ^ 2) $. Ad esempio, sorta ha un (n ^ 2) $ runtime $ O, perché selezionando il $ k $ esimo elemento richiede $ nk $ confronti, per un totale di $ n (n-1) / 2 $ confronti. In realtà, il numero di confronti è sempre esattamente $ n (n-1) / 2 $, che cresce da $ n ^ 2 $. Così possiamo essere più precisi circa la complessità temporale di selection sort:. È $ \ Theta (n ^ 2) $

Ora prendete merge sort . Merge sort è anche quadratica ($ O (n ^ 2) $). Questo è vero, ma non molto preciso. Merge sort, infatti, ha un tempo di esecuzione di $ O (n \: \ mathrm {} lg (n)) $ nel peggiore dei casi. Come selection sort, il flusso di lavoro merge di sorta è essenzialmente indipendente dalla forma dell'ingresso, e il suo tempo di esecuzione è sempre $ n \: \ mathrm {lg} (n) $ fino ad un fattore moltiplicativo costante, cioè è $ \ Theta (n \: \ mathrm {} lg (n)). $

Quindi, considerare quicksort . Quicksort è più complex. E 'certamente $ O (n ^ 2) $. Inoltre, il caso peggiore di quicksort è quadratica: caso peggiore è $ \ Theta (n ^ 2) $. Tuttavia, il miglior caso di quicksort (quando l'input è già ordinato) è lineare: il meglio che possiamo dire con un limite inferiore al Quicksort, in generale, è di $ \ Omega (n) $. Non voglio ripetere la prova qui, ma il medio complessità di quicksort (la medio impiegato su tutte le possibili permutazioni di ingresso) è di $ \ Theta (n \: \ mathrm {} lg (n)). $

Non ci sono risultati generali sulla complessità di algoritmi di ordinamento in impostazioni comuni. Si supponga che un algoritmo di ordinamento può confrontare solo due elementi alla volta, con un sì o nessun risultato (sia $ x \ le y $ o $ x> y $). Poi è ovvio che tempo di esecuzione di qualsiasi algoritmo di ordinamento è sempre $ \ Omega (n) $ (dove $ n $ è il numero di elementi da ordinare), poiché l'algoritmo deve confrontare ogni elemento almeno una volta di sapere dove si adatta . Questo limite inferiore può essere soddisfatta, per esempio, se l'input è già ordinato e l'algoritmo semplicemente confronta ogni elemento con il successivo e li tiene in ordine (che è $ n-1 $ confronti). Ciò che è meno evidente è che il massima tempo di esecuzione è necessariamente $ \ Omega (n \: \ mathrm {} lg (n)) $. E 'possibile che l'algoritmo a volte fare un minor numero di confronti, ma ci deve essere una costante $ K $ tale che per ogni dimensione di input $ n $, v'è almeno un ingresso su cui l'algoritmo ha più di $ K n \ mathrm { lg} (n) $ confronti. L'idea della dimostrazione è quello di costruire l'albero decisionale dell'algoritmo, cioè di seguire le decisioni l'algoritmo prende dal risultato di ogni confronto. Dal momento che ogni confronto restituisce un sì-o-no risultato, la struttura decisionale è un albero binario. Ci sono $ n $ possibili permutazioni dell'ingresso, e le esigenze algoritmo per distinguere tra tutti loro, quindi la dimensione della struttura decisionale è di $ n! $. Dal momento che l'albero è un albero binario, ci vuole una profondità di $ \ Theta (\ mathrm {lg} (n)!) = \ Theta (n \: \ mathrm {lg} (n)) $ per adattarsi a tutti questi nodi. La profondità è il numero massimo di decisioni che l'algoritmo prende, in modo da correre l'algoritmo coinvolge almeno questo molti paragoni: il tempo massimo di esecuzione è di $ \ Omega (n \: \ mathrm {lg} (n)). $

¹ _{O altro consumo di risorse come lo spazio di memoria. In questa risposta, ritengo solo tempo di esecuzione.}

Answer 3

In genere $ O $ è usato per affermare superiore limiti (una stima dall'alto), mentre $ \ Omega $ è utilizzato per stato di risparmio limiti (una stima dal basso), e $ \ Theta $ viene utilizzato quando corrispondono , nel qual caso è possibile utilizzare $ \ Theta $ al posto di loro (di solito) per indicare il risultato.