Je comprends mathématiquement $ f (n) \ in O (g (n)) $: $ f (n) $ ne comprend pas croître plus vite que $ g (n) $. Plus formellement, $ \ existe c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
De même, $ f (n) \ in \ Theta (g (n)) $ signifie que $ f (n) $ croît approximativement aussi vite que $ g (n) $. ie $ f (n) \ in O (g (n)), \ Omega (g (n)) $.
Ce que je ne comprends pas, cest pourquoi les gens utilisent big Oh pour la durée de un algorithme? Ne devrions-nous pas utiliser de gros Thêta. Lorsque nous disons « Durée dexécution » dun algorithme, nous nous référons au temps dexécution le plus défavorable, cest-à-dire $ T (n) = max \ {ALG (x): | x | = n \} $.
Donc, ex: le pire des cas dexécution dune recherche linéaire sur une entrée de taille $ n $ ($ n $ éléments et une valeur cible) est $ \ Theta (n) $ et $ O (n) $, mais $ \ Theta (n) $ donne plus dinformations. Alors, pourquoi les livres dalgorithmes utilisent-ils $ O (n) $ et non $ \ Theta (n) $.
Commentaires
- Souvent ‘ car nous pouvons simplement ‘ t obtenir une borne big-thêta serrée sur le temps dexécution dun algorithme. Si un algorithme est suffisamment compliqué, il se peut que le mieux que nous puissions faire est de dire que le temps dexécution est, disons $ O (n ^ {n!}) $ Où en réalité il pourrait être $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Raisons historiques.
- » Ce que je fais ‘ Pourquoi les gens utilisent-ils big Oh pour la durée dexécution dun algorithme? ‘ ne devrait pas utiliser de gros Thêta. » – Oui. Attendez, non, nous devrions faire des déclarations encore plus précises. Mais si je dois choisir, oui, $ \ Theta $!
Answer
Je vois deux raisons pour lesquelles les gens préfèrent Big Oh à Big Theta:
- La complexité dexécution dun algorithme nest pas nécessairement définie comme la complexité dexécution du pire des cas. Vous pouvez également le voir comme le runtime sur une instance arbitraire de longueur $ n $. Ensuite, si vous écrivez par exemple que le runtime $ t (n) $ dun algorithme est dans $ \ mathcal {O} (n ^ 2) $ cela signifie que quelle que soit lentrée de longueur $ n $ que vous choisissez, elle augmentera toujours asymptotiquement plus lent que la fonction $ c \ cdot n ^ 2 $ pour une constante $ c $ – nous faisons donc évidemment une déclaration sur le pire des cas dexécution.
- Parfois, lorsque vous analysez le runtime. complexité dun algorithme, vous ne savez pas avec certitude si la complexité du pire des cas que vous donnez est vraiment serrée. Prenons par exemple la complexité dexécution de la multiplication de matrice . Là, on ne sait toujours pas si le runtime $ n ^ {2.3728639} $ est vraiment le pire des cas. Et donc le runtime est connu pour être dans $ \ mathcal {O} (n ^ {2.3728639}) $ alors quil » Je ne sais pas si cest dans $ \ Theta (n ^ {2.3728639}) $.
Mais aussi, vous avez raison de dire que dans certains cas, il serait préférable de fournir un Big Theta lié à un Big Oh lié.
Commentaires
- Annonce 1: Lecteurs, soyez prudent de ne pas trop en lire !
Réponse
Une limite supérieure (bâclée) est plus facile à prouver quune limite supérieure serrée, sans parler des limites supérieures et inférieures.
Lexécution de certains algorithmes peut « t être donné avec la même fonction que la borne supérieure / inférieure. Par exemple. les algorithmes de tri simples sont $ O (n ^ 2) $, mais ont une borne inférieure $ \ Omega (n) $.
Certains insistent pour essayer de donner des performances en termes asymptotiques via $ \ sim $, où $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(par exemple, en tant que moyenne, ou pire des cas, en terme de nombre dopérations critiques, telles que des comparaisons lors du tri). Cest-à-dire une marge de manœuvre, mais pas de constantes (peut-être énormes) balayées sous le tapis.
Commentaires
- Quand nous nous référons à » runtime « , nous faisons référence à quelque chose comme le meilleur temps dexécution, le pire cas dexécution et le temps dexécution moyen. Exemple: Quicksort a le temps dexécution $ \ Theta (n ^ 2) $ le plus défavorable et le temps dexécution $ \ Theta (n) $ meilleur cas. Les asymptotiques sont définies à droite des fonctions.
Réponse
Si big-Theta peut être utilisé à la place de big- Oh, il devrait être utilisé à moins que cela ajoute une difficulté inutile à la compréhension. Il y a des cas subtils où big-Theta ne peut pas être utilisé à la place de big-Oh, par exemple:
Considérez le problème suivant: trier les tableaux de longueur paire. Le programme pour résoudre ce problème pourrait être: si la longueur du tableau est impaire, quittez immédiatement, si la longueur du tableau est paire, effectuez un tri par bulles. Quel est le pire des cas dexécution de cet algorithme?
Cest sûrement $ O (n ^ 2) $, mais ce nest PAS $ \ Omega (n ^ 2) $ au sens $ \ Omega $ est généralement défini. Au lieu de cela, son temps dexécution le plus défavorable est « $ \ Omega (n ^ 2) $ infiniment souvent » pour ainsi dire (avertissement: terminologie non standard).
Réponse
Dans la réponse de « pourquoi les livres dalgorithmes utilisent-ils big-Oh et non Theta »:
Big-Oh est utilisé pour lanalyse du pire des cas et Big-Omega pour le meilleur des cas uniquement. Mais en analysant en termes de Big-Theta, nous parlons simultanément de Big-Oh & Big-Omega.
ie. Pour Big-Theta, il est nécessaire que Big-Oh == Big-Omega, sinon nous ne pouvons pas parler de Big-Theta.
Donc, partout où (livre / tout document) vous voyez lutilisation de Big-Theta, ils donnent la complexité des deux Big-Oh & Big-Omega (et les deux sont égaux aussi). Mais dans de nombreux cas, ils ne sont pas égaux alors nous nutilisons que Big- Oh juste pour le pire des cas.