Ho capito matematicamente $ f (n) \ in O (g (n)) $: $ f (n) $ no crescono più velocemente di $ g (n) $. Più formalmente, $ \ esiste c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
Allo stesso modo, $ f (n) \ in \ Theta (g (n)) $ significa che $ f (n) $ cresce approssimativamente alla stessa velocità di $ g (n) $. cioè $ f (n) \ in O (g (n)), \ Omega (g (n)) $.
Quello che non capisco è perché le persone usano big Oh per il tempo di esecuzione di un algoritmo? Non dovremmo usare un Theta grande. Quando diciamo “Tempo di esecuzione” di un algoritmo, ci riferiamo al tempo di esecuzione del caso peggiore, ad esempio $ T (n) = max \ {ALG (x): | x | = n \} $.
Quindi, es: il tempo di esecuzione del caso peggiore della ricerca lineare su un input di dimensione $ n $ ($ n $ elementi e un valore di destinazione) è $ \ Theta (n) $ e $ O (n) $, ma $ \ Theta (n) $ fornisce ulteriori informazioni. Allora, perché i libri degli algoritmi usano $ O (n) $ e non $ \ Theta (n) $.
Commenti
- Spesso ‘ s perché semplicemente non possiamo ‘ ottenere uno stretto limite big-theta sul tempo di esecuzione di un algoritmo. Se un algoritmo è sufficientemente complicato, potrebbe accadere che il meglio che possiamo fare sia dire che il tempo di esecuzione è, diciamo $ O (n ^ {n!}) $ Dove in realtà potrebbe essere $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Motivi storici.
- ” Cosa indosso ‘ Non capisco perché le persone usano big Oh per il tempo di esecuzione di un algoritmo? ‘ t utilizzare Theta grande. ” – Sì. Aspetta, no, dovremmo fare affermazioni ancora più precise. Ma se devo scegliere, sì, $ \ Theta $!
Answer
Vedo due motivi per cui le persone preferiscono Big Oh a Big Theta:
- La complessità di runtime di un algoritmo è non necessariamente definita come la complessità di runtime del caso peggiore. Potresti anche vederlo come runtime su unistanza arbitraria di lunghezza $ n $. Quindi, se scrivi ad esempio che il runtime $ t (n) $ di un algoritmo è in $ \ mathcal {O} (n ^ 2) $ questo significa che qualunque input di lunghezza $ n $ scegli, crescerà sempre asintoticamente più lenta della funzione $ c \ cdot n ^ 2 $ per una certa $ c $ costante, quindi stiamo ovviamente facendo unaffermazione sul runtime del caso peggiore.
- A volte quando analizzi il runtime complessità di un algoritmo che non sai con certezza se la complessità nel caso peggiore che stai dando è davvero stretta. Prendi ad esempio la complessità di runtime della moltiplicazione di matrici . Là non è ancora chiaro se il runtime $ n ^ {2.3728639} $ sia davvero il caso peggiore. E quindi si sa che il runtime è in $ \ mathcal {O} (n ^ {2.3728639}) $ mentre ” non sono sicuro che sia in $ \ Theta (n ^ {2.3728639}) $.
Ma hai anche ragione che in alcuni casi sarebbe meglio fornire un Big Theta legato a un limite di Big Oh.
Commenti
- Annuncio 1: lettori, fate attenzione per non leggere troppo in questo !
Risposta
Un limite superiore (sciatto) è più facile da dimostrare di un limite superiore stretto, per non parlare dei limiti e inferiori superiori.
Il runtime di alcuni algoritmi può “t essere dato con la stessa funzione del limite superiore / inferiore. Per esempio. semplici algoritmi di ordinamento sono $ O (n ^ 2) $, ma hanno un limite inferiore $ \ Omega (n) $.
Alcuni insistono nel cercare di fornire prestazioni in termini asintotici tramite $ \ sim $, dove $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(diciamo come media, o caso peggiore, in termini di numero di alcune operazioni critiche, come i confronti durante lordinamento). Vale a dire, spazio di manovra, ma nessuna (forse gigantesca) costante sotto il tappeto.
Commenti
- Quando ci riferiamo a ” runtime “, ci riferiamo a qualcosa come tempo di esecuzione nel caso migliore, tempo di esecuzione nel caso peggiore e tempo di esecuzione nel caso medio. Ad esempio: Quicksort ha $ \ Theta (n ^ 2) $ tempo di esecuzione nel caso peggiore e $ \ Theta (n) $ tempo di esecuzione nel caso migliore. Gli asintotici sono definiti sulle funzioni a destra.
Answer
Se big-Theta può essere usato al posto di big- Oh, dovrebbe essere usato a meno che non aggiunga inutili difficoltà di comprensione. Ci sono alcuni casi impercettibili in cui big-Theta non può essere usato al posto di big-Oh, ad esempio:
Considera il seguente problema: ordina array di lunghezza pari. Il programma per risolvere questo problema potrebbe essere: se la lunghezza dellarray è dispari, esci immediatamente, se la lunghezza dellarray è pari esegui il Bubble sort. Qual è il tempo di esecuzione nel caso peggiore di questo algoritmo?
È sicuramente $ O (n ^ 2) $, ma NON è $ \ Omega (n ^ 2) $ nel senso $ \ Di solito viene definito Omega $, mentre il suo tempo di esecuzione nel caso peggiore è “$ \ Omega (n ^ 2) $ infinitamente spesso” per così dire (attenzione: terminologia non standard).
Risposta
Nella risposta di “perché i libri di algoritmi usano big-Oh e non Theta”:
Big-Oh viene utilizzato per lanalisi del caso peggiore e Big-Omega viene utilizzato solo per il caso migliore. Ma analizzando in termini di Big-Theta, parliamo simultaneamente di Big-Oh & Big-Omega.
es. Per Big-Theta è necessario che Big-Oh == Big-Omega, altrimenti non possiamo “non parlare di Big-Theta.
Quindi, ovunque (libro / qualsiasi documento) vedi luso di Big-Theta, stanno dando la complessità di entrambi Big-Oh & Big-Omega (ed entrambi sono uguali). Ma molti casi non sono uguali quindi usiamo solo Big- Oh solo nel peggiore dei casi.