Mergesort durée Bigo

Question

Le manuel « Les algorithmes pour inamical Assistants » Rogue affirme le temps d'exécution de fusion trier est O (n ^ 4). Est-ce correct réclamation?

Solution: Oui. Cette revendication est techniquement correcte, car O (n ^ 4) ne donne qu'une partie supérieure lié pour combien de temps l'algorithme prend. Cependant, il est une réponse odieusement inutile, puisque le serré lié est Θ(n log n).

Je ne comprends pas tout à fait ce que la solution est déclarant. Comment peut-O (n ^ 4) correct?

Answer 1

notation Big O est un majorant le pire des cas pour un temps d'exécution de l'algorithme.

Depuis O (n ^ 4) est supérieur au pire moment de cas de mergesort est techniquement correcte parce qu'elle ne fournit une borne - à savoir. Mergesort aura jamais une performance pire que O (n ^ 4).

Cependant, il est inutile parce qu'une meilleure expression du temps d'exécution est O (n log n), qui est le « plus serré » lié pour le tri de fusion

Answer 2

Big-O est un ensemble, qui comprend tout ce qui fonctionne aussi vite que (foo) ou plus rapide. Petit-O est un ensemble de choses qui fonctionnent strictement plus vite que (foo). Bien qu'il soit correct de dire mergesort est O (n ^ 4), ce n'est pas très utile, car il est Theta (n log n). Dire que mergesort est o (n ^ 4) est légèrement plus utile, parce que peu o notation est jamais utilisé pour impliquer grand-theta exécution.

D'autres questions compliquant, grand-O est souvent utilisé lorsque grand-thêta serait plus approprié, juste parce que la plupart des claviers ne sont pas thêta.