Big-oh vs big-theta

Question

Double Possible:
Quelle est la différence entre Θ(n) et O(n)?

Il me semble que quand les gens parlent de la complexité de l'algorithme de manière informelle, ils parlent de la grande-oh. Mais dans les situations formelles, je vois souvent des grands-thêta avec parfois des grands-oh jeté dans. Je sais que mathématiquement quelle est la différence entre les deux, mais en anglais, en quoi la situation serait à l'aide de grand-oh, quand vous voulez dire grand-theta-être incorrect, ou vice-versa (par exemple, l'algorithme serait appréciée)?

Bonus: pourquoi des gens apparemment toujours utiliser de grands-oh, quand parler de façon informelle?

Answer 1

Big-O est une limite supérieure.

Grand-Theta est serré, lié, c'est à dire supérieure et de limite inférieure.

Quand les gens seulement s'inquiéter quel est le pire qui peut arriver, big-O est suffisant; par exemple il est dit que "il ne peut pas être bien pire que cela". Le resserrement de la tenue de respecter le mieux, bien sûr, mais un serré lié n'est pas toujours facile à calculer.

Voir aussi

• Wikipedia/Notation Grand O

Questions connexes

• Quelle est la différence entre Θ(n) et O(n)?

---

La citation suivante tirée de Wikipédia éclaire:

De manière informelle, en particulier dans l'informatique, le Big O souvent, la notation est autorisé à être un peu abusé pour décrire une asymptotique serré lié où en utilisant de Grandes Thêta notation pourrait être plus factuel approprié dans un contexte donné.

Par exemple, lorsque l'on considère une fonction T(n) = 73n³+ 22n²+ 58, tous les éléments suivants sont généralement acceptables, mais l'étanchéité de la limite (c'est à dire, les points 2 et 3 ci-dessous) sont généralement fortement préféré plus de laxisme de la limite (c'est à dire, le point 1 ci-dessous).

1. T(n) = O(n¹⁰⁰), qui est identique à l' T(n) ∈ O(n¹⁰⁰)
2. T(n) = O(n³), qui est identique à l' T(n) ∈ O(n³)
3. T(n) = Θ(n³), qui est identique à l' T(n) ∈ Θ(n³)

L'équivalent anglais des états sont respectivement:

1. T(n) pousse asymptotiquement pas plus vite que n¹⁰⁰
2. T(n) pousse asymptotiquement pas plus vite que n³
3. T(n) pousse asymptotiquement aussi vite qu' n³.

Ainsi, alors que les trois déclarations sont vraies, progressivement de plus en plus l'information est contenue dans chaque. Dans certains domaines, toutefois, la notation Grand O (balles numéro 2 dans la liste ci-dessus) serait plus couramment utilisés que le Grand Thêta notation (balles numéro 3 dans le les listes ci-dessus) parce que les fonctions qui se développent plus lentement sont plus souhaitables.

Answer 2

Je suis mathématicien et j'ai vu et besoin de gros-O, grand-Thêta, et le grand-Omega notation encore et encore, et pas seulement de la complexité des algorithmes. Comme les gens ont dit, grand-Theta est une double limite. Strictement parlant, il faut l'utiliser quand vous voulez expliquer que c'est bien un algorithme peut le faire, et que, soit que l'algorithme ne peut pas faire mieux ou qu'aucun algorithme ne peut faire mieux. Par exemple, si vous dites "Tri nécessite Θ(n(log n) comparaisons pour le pire des cas, l'entrée", alors vous êtes en expliquant qu'il existe un algorithme de tri qui utilise O(n(log n) comparaisons pour toute entrée; et que, pour chaque algorithme de tri, il y a une entrée qui l'oblige à faire Ω(n(log n) comparaisons.

Maintenant, une petite raison que les gens utilisent des O au lieu de Ω est à déposer des avertissements au sujet de pire ou de la moyenne des cas. Si vous dites "tri nécessite O(n(log n) comparaisons", l'énoncé reste vrai pour favorable d'entrée. Un autre étroites raison est que, même si un algorithme pour faire X prend du temps Θ(f(n)), un autre algorithme peut faire mieux, si vous pouvez seulement dire que la complexité de X lui-même est O(f(n)).

Cependant, il n'est plus de raison que les gens de manière informelle utilisation O., Au niveau de l'être humain, c'est une douleur pour toujours deux faces états lorsque l'inverse côté est "évident" à partir du contexte. Depuis que je suis mathématicien, j'ai l'idéal serait d'être toujours attentif à dire "je vais prendre un parapluie si et seulement si il pleut" ou "je peux jongler avec 4 balles, mais pas 5" au lieu de "je vais prendre un parapluie s'il pleut" ou "je peux jongler avec 4 balles". Mais les autres moitiés de telles déclarations sont souvent bien évidemment prévu ou ne veut pas. C'est juste la nature humaine pour être bâclée sur l'évidence. C'est déroutant de couper les cheveux en quatre.

Malheureusement, dans un rigoureux de la région telles que les mathématiques ou de la théorie des algorithmes, c'est aussi déroutant de ne pas couper les cheveux en quatre. Les gens vont inévitablement dire O quand ils devraient avoir dit Ω ou de Θ. Ignorant les détails parce qu'ils sont "évidentes" conduit toujours à des malentendus. Il n'y a pas de solution pour cela.

Answer 3

Parce que mon clavier a une touche O.
Il n'a pas de touche Θ ou Ω.

Je pense que la plupart des gens sont pareillement paresseux et utilisent O quand ils veulent dire Θ car il est plus facile de taper.

Answer 4

L'une des raisons pourquoi big O s'habitue tellement est du genre parce qu'il s'habitue tellement. Beaucoup de gens voient la notation et de penser qu'ils savent ce que cela signifie, puis l'utiliser (à tort) eux-mêmes. Cela arrive souvent avec des programmeurs dont l'éducation formelle ne suis allé jusqu'à présent - j'ai été une fois coupable moi-même.

Un autre, parce que c'est plus facile de taper un grand O sur la plupart des non-grecs claviers qu'un gros thêta.

Mais je pense que beaucoup est à cause d'une sorte de paranoïa. J'ai travaillé liées à la défense de programmation pour un peu (et elle savait très peu de choses sur l'algorithme de l'analyse à l'époque). Dans ce scénario, le pire des cas, la performance est toujours ce qui intéresse les gens, parce que le pire des cas pourrait bien se produire au mauvais moment. Il n'a pas d'importance si la probabilité que cela arrive est par exemple beaucoup moins que la probabilité de tous les membres d'un équipage de navire de la souffrance un coup de fluke crise cardiaque au même moment -, il pourrait encore se produire.

Bien sûr, beaucoup d'algorithmes ont leur pire des cas très des circonstances ordinaires - l'exemple classique étant l'insertion dans l'ordre dans un arbre binaire de ce qui est effectivement une liste liée individuellement. Un "vrai" évaluation de la performance moyenne des besoins à prendre en compte la fréquence relative des différents types d'entrée.

Answer 5

Parce qu'il existe des algorithmes dont le meilleur des cas est rapide, et donc techniquement, c'est un gros O, pas un grand Theta.

Big O est une limite supérieure , Big Theta est une relation d'équivalence .