Exemple d'un algorithme où un terme de faible ordre domine le runtime pour toute entrée pratique?

La notation Big-O cache des facteurs constants, il existe donc certains algorithmes qui sont impossibles pour toute taille d'entrée raisonnable car le coefficient sur le terme est si énorme.$O(n)$$n$

Existe-t-il des algorithmes connus dont le temps d'exécution est mais avec un terme ordre inférieur qui est si énorme que pour des tailles d'entrée raisonnables, il domine complètement le temps d'exécution? Je voudrais utiliser un algorithme comme celui-ci et un exemple dans un cours d'algorithmes, car cela donne une bonne raison pour laquelle la notation big-O n'est pas tout.o ( f ( n ) $O(f(n))$$o(f(n))$

Merci!

La cryptographie est un exemple, si elle est dégénérée. Par exemple, briser le cryptage AES est - tout ce que vous avez à faire est de trouver la bonne clé parmi un nombre fini, 2 128 ou 2 192 ou$O(1)$$2^{128}$$2^{192}$ en fonction de la tailleclé (supposant que suffisamment de texte brut est connu déterminer la clé sans ambiguïté). Cependant, même 2 128 opérations nécessiteraient tous les ordinateurs aujourd'hui (un milliard ou environ, faisant chacun environ un milliard d'opérations par seconde) plus que la durée de vie de l'univers (environ un milliard de milliards de secondes).$2^{256}$$2^{128}$

Une manière légèrement différente d'illustrer pourquoi le big-O n'est pas tout est de remarquer que nous utilisons parfois un algorithme différent pour les petites tailles d'entrée. Par exemple, prenez quicksort. Avec le bon choix de pivot (ce qui est une affaire délicate!), C'est . Quicksort fonctionne par division et conquête: chaque instance implique de faire beaucoup de tri de petits tableaux. Pour les petits tableaux, les méthodes quadratiques telles que le tri par insertion fonctionnent mieux. Ainsi, pour de meilleures performances, un tri rapide d'un grand tableau implique de nombreuses exécutions de tri par insertion pour les petites tailles.$O(n \lg n)$

Deux exemples me viennent à l'esprit du domaine de la complexité paramétrée et des algorithmes FPT. Ce n'est peut-être pas exactement ce que vous recherchez, mais voici.

Considérons un problème de graphique, tel que 3-COLORING ou HAM-CYCLE. Les deux problèmes peuvent être exprimés en logique monadique du second ordre, et peuvent donc être décidés en temps linéaire de graphiques avec une largeur d'arbre bornée. C'est le résultat de Bruno Courcelle , mais l'algorithme qui en résulte est loin d'être pratique.

$O(p^{9p/2})L$$O(p^{2p}L)$$p$$L$

quelque peu liés à votre question sont des algorithmes qui sont connus pour avoir de bonnes performances théoriquement mais qui ne sont pas utilisés sur des problèmes réels en raison de l'impraticabilité sur des instances plus petites. en d'autres termes, comme vous le demandez, la "performance annoncée" n'est possible qu'en théorie pour de grandes entrées, ce qui n'est pas le cas dans les applications pratiques. cela se reflète parfois dans les estimations Big-Oh, d'autres fois pas exactement. certains algorithmes ont de bonnes "performances" théoriques mais sont très logiquement complexes et n'ont jamais été implémentés par qui que ce soit, et donc les "performances" sur les tailles d'instances pratiques ne sont même pas connues, par exemple avec le problème de débit maximal .

• test de primalité en P via l'algorithme AKS

• Algorithme de multiplication matricielle de Coppersmith-winograd

• voir aussi les algorithmes de flux maximum de pointe sont-ils pratiques? tcs.se

• voir aussi des algorithmes puissants trop complexes pour implémenter tcs.se

• algorithmes galactiques blog RJLipton

C'est une blague mais ça a un côté sérieux ...

$O(n\log n)$$O(n^2)$