Notation asymptotique - n (log n) (log n) simplifie-t-il?

Question

Si j’ai un algorithme qui prend n log n étapes (par exemple, heapsort), les étapes prennent log n temps (par exemple, comparaison / échange de & "grands &"; entiers compris entre 0 et n -1), quelle est la liaison asymptotique pour l'ensemble du processus.

Évidemment, nous pouvons dire " n (log n) (log n) & ";, mais j'ai du mal à me convaincre que je ne peux pas simplifier ceci en &"; n log n " ;. En même temps, j'ai du mal à justifier l'instinct qui insiste pour que je puisse le faire.

Mon instinct est-il tout simplement faux?

MODIFIER

Il semble que mon exemple simple pour éviter de compliquer le problème ait compliqué le problème. Oh bien.

La vraie raison de la question est que j’ai souvent un algorithme standard avec une complexité connue, mais implémenté en utilisant des conteneurs sous-jacents différents, de sorte que les étapes individuelles sont O (log n) plutôt que O (1). Par exemple, l'algorithme de minimisation d'automate de Hopcrofts est O (n log n) - mais si vous commencez à utiliser des conteneurs d'arborescence binaire pour les états, les transitions et les résultats intermédiaires, les étapes deviennent elles-mêmes O (log n) - le O (n log n) est n'est plus valide car l'hypothèse d'accès O (1) n'est pas valide.

Néanmoins, les gens prétendent qu’il existe n états et m transitions, mais que n et m ont tendance à être liés linéairement pour les automates, en supposant que le nombre d’annotations de transition est constant et que les automates sont plus ou moins déterministes.

Je ne m'étais pas trop inquiété à ce sujet par le passé - les cas avec lesquels je travaille ne sont pas très gros. Mais bon, je fais une refactorisation majeure de mon code automate, et je me suis dit que je pourrais aussi bien faire les calculs correctement pour certains algorithmes clés.

MODIFIER

Je suis également de plus en plus convaincu que le " n (log n) (log n) " est faux.

Si a est O (b log b) où b est o (log c), quel est le a en termes de c?

Answer 1

Voici une preuve par contradiction:

Supposons qu'une fonction f (n) = n (log n) (log n). Supposons que nous pensons que c’est aussi thêta (n log n), c’est-à-dire qu’il existe un a pour lequel f (n) & Lt; = a * n log n est valable pour n grand.

Considérons maintenant f (2 ^ (a + 1)):

f (2 ^ (a + 1)) = 2 ^ (a + 1) * log (2 ^ (a + 1)) * log (2 ^ (a + 1)) = 2 ^ (a + 1 ) * log (2 ^ (a + 1)) * (a + 1), qui est nettement plus grand que a * 2 ^ (a + 1) * log (2 ^ (a + 1)), et nous avons une contradiction . donc f (n) n’est pas une fonction n log n.

Answer 2

En général, vous ne pouvez pas multiplier les complexités comme ceci: pour le tri par tas, N indique le nombre d'éléments dans le tas, alors que pour les grands entiers, N indique probablement la limite supérieure des valeurs possibles. En général, il n’est pas nécessaire de les relier, de sorte qu’il s’agit plutôt de N log N log M (où M est la plage que peuvent prendre les éléments).

Dans une application spécifique, très probablement, les grands entiers suivent une distribution spécifique. Par exemple, on peut savoir qu’ils sont tous inférieurs à 10 ^ 20. Si tel est le cas, les opérations de comparaison prennent un temps constant (déterminé par une limite supérieure de 10 ^ 20). Ensuite, log M est également constant et toute la complexité est en O (N log N).

Answer 3

Vous ne pourrez pas réduire n (log n) (log n) à n (log n) simplement parce que ce n'est pas une réduction par un facteur constant.

Qu'est-ce qui ne va pas avec 2 ^<=> ?

Answer 4

D'accord, la mesure de la complexité générale d'un programme est la suivante:

  

Complexité O (f (n)) signifie qu’il existe c, de sorte que le nombre des étapes de la machine de Turing correspondantes avant la fin ne dépasse pas c * f (n), où n est la longueur de entrée.

Dans cette définition, tout est pris en compte, car les nombres entiers peuvent être arbitrairement grands, et les opérations arithmétiques sur eux augmenteraient également la fonction sous O (n).

Mais si nous programmions directement les machines Turing, votre question ne se serait pas posée. Dans le monde réel, nous préférons résumer. Bien que nous calculions encore & Quot; pas & Quot; nécessaires au fonctionnement du programme, nous supposons que certaines opérations nécessitent une étape . Nous supposons que pour différentes raisons:

• Cela peut ressembler au travail réel de la CPU, où chaque addition d’entier sur 32 bits est bien une étape (et il existe des algorithmes qui en abusent, par exemple & "; dominateurs de bits"!! ") .
• Nous comparons différents algorithmes d'un même domaine (par exemple, en comparant les triages de tableaux en mesurant le nombre de comparaisons).

Dans ce cas (votre premier EDIT), si vous voulez concrétiser votre mesure de complexité, vous devez simplement multiplier les fonctions sous O. Si ce que vous pensiez prendre une étape considère maintenant comme prenant O (log N), La quantité d’étapes concrétisées augmente d’un facteur O (log N). La complexité totale est donc égale à O (N log N log N).

En ce qui concerne votre deuxième édition, la situation est différente. Laissez votre algorithme être une complexité de O (n log N). Mais vous savez que l’entrée consiste en M chiffres, chacun de log K chiffres, donc `N = O (M ) log K) (nous avons besoin de séparateurs de comptes, etc.). C'est mathématiquement correct d'écrire la complexité globale sous la forme O (M * log K * (log M + log log K)), il n'y a donc aucun problème ici. Mais en général, nous faisons abstraction des détails inutiles pour trouver une base commune permettant de comparer différents algorithmes.