Temps d'exécution de Mergesort BigO

Question

Le manuel de "Rogue Algorithms for Wizards" de Snape revendique le temps de fusion sort est O (n^4). Cette affirmation est-elle correcte?

Solution: Oui. Cette affirmation est techniquement correcte, car O (n^4) ne donne qu'un supérieur pour la durée de l'algorithme. Cependant, c'est une réponse désagréablement inutile, puisque la limite serrée est Θ(n log n).

Je ne comprends pas très bien ce que dit la solution. Comment O (n^4) peut-il être correct?

Answer 1

La notation Big O est une valeur supérieure dans le pire des cas pour un algorithme d'exécution.

Comme O (n^4) est au-dessus du pire cas de mergesort, il est techniquement correct car il fournit une limite - ie. Mergesort n'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 par fusion

Answer 2

Big-O est un ensemble, qui comprend tout ce qui fonctionne aussi vite que (foo) ou plus vite. Little-O est un ensemble de choses qui s'exécutent plus vite que (foo). Bien qu'il soit correct de dire que mergesort est O (n^4), ce n'est pas très utile, parce que c'est Theta (n log n). Dire que mergesort est o (n^4) est marginalement plus utile, parce que la notation little-o n'est jamais utilisée pour impliquer un runtime big-theta.

Encore plus compliqué, big-O est souvent utilisé lorsque big-theta serait plus approprié, juste parce que la plupart des claviers n'ont pas de thêta.