Existe-t-il des algorithmes réels qui surpassent considérablement les performances de la classe ci-dessous? [fermé]

39

Hier soir, je discutais avec un autre programmeur du fait que même si quelque chose peut être O (1), une opération qui est O (n) peut la surperformer s'il existe une constante de grande taille dans l'algorithme O (1). Il n'était pas d'accord, alors je l'ai amené ici.

Existe-t-il des exemples d’algorithmes qui surpassent considérablement ceux de la classe inférieure? Par exemple, O (n) étant plus rapide que O (1) ou O (n 2 ) étant plus rapide que O (n).

Mathématiquement, cela peut être démontré pour une fonction avec une limite supérieure asymptotique, lorsque vous ignorez les facteurs constants, mais existe-t-il de tels algorithmes dans la nature? Et où pourrais-je en trouver des exemples? Quels types de situations sont-ils utilisés?

KyleWpppd
la source
15
Même pour les "gros" algorithmes, plus petit n'est pas nécessairement meilleur. Par exemple, l’élimination gaussienne est O (n ^ 3), mais il existe des algorithmes qui peuvent le faire dans O (n ^ 2), mais le coefficient pour l’algorithme de temps quadratique est si énorme que les gens optent simplement pour le O (n ^ 2). 3) un.
BlackJack
11
Vous devez ajouter "... pour des problèmes concrets" ou des problèmes du même genre, pour en faire une question sensée. Sinon, vous devez seulement faire nassez grand pour compenser la constante (qui est le point de la notation big-O).
starblue
8
Ne prenez pas la notation big-O pour la vitesse.
Codisme
16
Le but de la notation big-O n'est pas de vous dire à quelle vitesse tourne un algorithme, mais bien comment il évolue.
BlueRaja - Danny Pflughoeft
4
Je suis surpris que personne n'ait mentionné l'algorithme Simplex pour résoudre LP. Il a un cas extrême exponentiel avec une durée d'exécution linéaire attendue. En pratique, c'est assez rapide. Il est trivial de construire un problème qui présente également le pire temps d'exécution. En outre, il est fortement utilisé.
ccoakley

Réponses:

45

Recherches dans de très petites tables de données fixes. Une table de hachage optimisée peut être O (1) et pourtant plus lente qu'une recherche binaire ou même une recherche linéaire en raison du coût du calcul du hachage.

Loren Pechtel
la source
14
Plus précisément, la recherche dans la table de hachage est O (m), où m est la taille de la clé. Vous ne pouvez appeler que O (1) si la taille de la clé est constante. En outre, cela est généralement amorti - sinon, la table ne peut pas grossir / rétrécir. Les arbres ternaires peuvent souvent battre les tables de hachage pour les recherches de chaînes dans des contextes dans lesquels les chaînes ne sont souvent pas trouvées. La recherche d'arborescence ternaire découvre souvent que la clé n'est pas présente tout en vérifiant le ou les premier (s) caractère (s) de la chaîne. hashtable version n'a pas encore calculé le hachage.
Steve314
2
J'adore la réponse de Loren Pechtel et le premier commentaire de Steve314. J'ai effectivement vu cela arriver. Si vous créez une classe Java avec une méthode hashcode () qui prend trop de temps pour renvoyer la valeur de hachage (et ne la met pas en cache / ne peut pas la mettre en cache), utilisez des instances d'une telle classe dans une collection de types de hachage (comme HashSet) rendra cette collection beaucoup plus lente qu'une collection de type tableau (comme ArrayList).
Shivan Dragon
1
@ Steve314: pourquoi supposez-vous que les fonctions de hachage sont O (m) où m est la taille de la clé? Les fonctions de hachage peuvent être O (1) même si vous utilisez des chaînes (ou un autre type complexe). Il n’ya pas trop de valeur à placer dans une définition formelle, car la simple réalisation de la fonction de hachage pourrait considérablement modifier la complexité si une mauvaise structure de données (table de hachage) est choisie pour votre entrée (la taille de la clé est imprévisible).
Codisme
1
@ Steve314: Notez que j'ai dit tables de données fixes. Ils ne grandissent pas. En outre, vous n'obtenez les performances O (1) d'une table de hachage que si vous pouvez optimiser la clé pour éviter les collisions.
Loren Pechtel
1
@ Loren - strictement, si la table a une taille fixe, vous pouvez consacrer un maximum de temps constant à la recherche d'un espace libre. Autrement dit, vous pouvez tout au plus vérifier les n-1 emplacements déjà remplis, n étant la taille constante de la table. Donc, une table de hachage de taille fixe est vraiment O (1), sans avoir besoin d'une analyse amortie. Cela ne signifie pas que vous ne vous souciez pas de ralentir les accès au fur et à mesure que la table se remplit, mais seulement que ce n'est pas ce que Big O exprime.
Steve314
25

Multiplication matricielle. L'algorithme naïf O (n ^ 3) est souvent utilisé en pratique aussi rapidement que O (n ^ 2.8) de Strassen pour les matrices de petite taille; et Strassen est utilisé à la place de l'algorithme Coppersmith – Winograd de O (n ^ 2.3) pour les matrices plus grandes.

Peter Taylor
la source
2
Coppersmith-Winograd n’est JAMAIS utilisé. Sa mise en œuvre serait une tâche horrible en soi et la constante est si mauvaise qu'elle serait irréalisable, même pour les problèmes matriciels scientifiques modernes.
tskuzzy
24

Un exemple simple est la différence entre différents algorithmes de tri. Mergesort, Heapsort et quelques autres sont O (n log n) . Quicksort est le pire cas O (n ^ 2) . Mais souvent, Quicksort est plus rapide et, en fait, il fonctionne comme O (n log n) . Plus d' info .

Un autre exemple est la génération d’un seul numéro de Fibonacci. L'algorithme itératif est O (n) , tandis que l'algorithme basé sur la matrice est O (log n) . Néanmoins, pour les quelques milliers de premiers nombres de Fibonacci, l’algorithme itératif est probablement plus rapide. Cela dépend aussi de la mise en œuvre bien sûr!

Les algorithmes offrant de meilleures performances asymptotiques peuvent contenir des opérations coûteuses qui ne sont pas nécessaires avec un algorithme moins performant, mais des opérations plus simples. En fin de compte, la notation O ne nous dit quelque chose à propos de la performance que lorsque l'argument sur lequel elle opère augmente considérablement (approche de l'infini).

molf
la source
Ceci est une excellente explication de Big-O, mais ne résout pas le problème de la question, qui est pour des cas spécifiques où un algorithme O (n) sera plus rapide qu'un O (1).
KyleWpppd
Le numéro un de Fibonacci est légèrement éteint. La taille de sortie est exponentielle dans la taille d'entrée, il s'agit donc d'une différence entre O (lg n * e ^ n) et O (lg lg n * e ^ n).
Peter Taylor
Addenda: au mieux. L'algorithme basé sur la matrice effectue une multiplication avec des nombres de l'ordre de 1,5 ^ n, de sorte que O (lg lg n * ne ^ n) pourrait être la meilleure borne prouvable.
Peter Taylor
1
De toute façon, Quicksort est généralement décrit comme une performance attendue - le cas le plus défavorable est assez improbable pour les entrées aléatoires, et intégrer une certaine aléatoire dans une sélection au préalable ou dans le pivot signifie que le cas le plus défavorable est très improbable pour des tailles d’entrée significatives. Le cas le plus défavorable est moins pertinent que le fait que le tri rapide soit (1) très simple et (2) très convivial en mémoire cache, les deux conduisant à des facteurs constants nettement meilleurs que dans de nombreux autres algorithmes de tri.
Steve314
(2) est précisément le type de considération externe à prendre en compte lorsque l’on examine la performance big-O. Algorithmiquement, Mergesort devrait toujours surpasser Quicksort, mais l’utilisation des ressources et la localité du cache inversent généralement leurs performances.
Dan Lyons
18

Remarque: veuillez lire les commentaires de @ back2dos ci-dessous et d'autres gourous, car ils sont en fait plus utiles que ce que j'ai écrit - Merci à tous les contributeurs.

Je pense que dans le tableau ci-dessous (tiré de: Big O notation , recherchez "La nature pessimiste des algorithmes:"), vous pouvez voir que O (log n) n’est pas toujours meilleur que, disons, O (n). Donc, je suppose que votre argument est valable.

Pic-1

Emmad Kareem
la source
6
La question visait des exemples spécifiques d’algorithmes dans le monde réel. Cela n'a pas comme tel.
Megan Walker
19
Vous ne voyez rien sur ce graphique, cela répondrait à la question. C'est trompeur. Ce graphique ne fait que représenter graphiquement les fonctions y = 1, y = log xetc., ainsi que l'intersection de y = 1et y = xconstitue en fait le point (1,1). Si cela était vraiment correct, il vous dirait que des algorithmes plus complexes peuvent être plus rapides pour 0 à 2 entrées, ce que les gens ne se soucient guère de faire. Ce que le graphique omet complètement de prendre en compte (et d'où provient la différence de performance perceptible en question) est un facteur constant.
back2dos
@Samuel Walker, merci pour le commentaire. Le lien fourni (Link-1) contient quelques exemples d'algorithmes par catégorie.
NoChance
5
@ back2dos: le graphique seul ne répond pas à la question, mais peut être utilisé pour y répondre. La forme de chaque fonction affichée est la même pour toute échelle et tout facteur constant. Le graphique montre qu’une combinaison de fonctions donnée donne une gamme d’entrées pour laquelle l’une est plus petite et une plage d’entrées pour l’autre.
Jan Hudec
2
@ dan_waterworth, vous avez raison, je vais concéder ce point et supprimer ce commentaire. Néanmoins, la réponse est fausse ou trompeuse à deux égards: 1) L’objectif principal de Big-O est qu’il donne une limite supérieure à la complexité; cela n'a de sens que pour les grands n parce que nous rejetons explicitement les termes plus petits qui sont submergés par le terme le plus important au fur et à mesure que n grandit. 2) Le but de la question est de trouver des exemples de deux algorithmes où l'un avec la borne Big-O la plus élevée surpasse un autre avec une borne la plus basse. Cette réponse échoue car elle ne donne aucun exemple.
Caleb
11

Pour les valeurs pratiques de n, oui. Cela revient souvent dans la théorie CS. Il existe souvent un algorithme compliqué qui offre des performances techniquement meilleures, mais les facteurs constants sont si importants qu’il est impossible de le rendre pratique.

Un jour, mon professeur de géométrie informatique a décrit un algorithme permettant de trianguler un polygone en temps linéaire, mais il a conclu avec "très compliqué. Je ne pense pas que quiconque l'ait réellement implémenté" (!!).

En outre, des tas fibonacci ont de meilleures caractéristiques que des tas normaux, mais ne sont pas très populaires parce qu'ils ne réussissent pas aussi bien dans la pratique que des tas réguliers. Cela peut se répercuter sur d'autres algorithmes utilisant des tas - par exemple, les plus courts chemins de Dijkstra sont mathématiquement plus rapides avec un tas de fibonacci, mais généralement pas dans la pratique.

Gabe Moothart
la source
C'est plus rapide pour les énormes graphiques de l'ordre de 100 000 sommets environ.
tskuzzy
Les tas de Fibonacci étaient aussi ma première (deuxième) pensée.
Konrad Rudolph
10

Comparez l'insertion dans une liste chaînée et l'insertion dans un tableau redimensionnable.

La quantité de données doit être assez grande pour que l'insertion dans la liste chaînée O (1) en vaille la peine.

Une liste liée a une surcharge supplémentaire pour les prochains pointeurs et déréférences. Un tableau redimensionnable doit copier des données. Cette copie est O (n), mais en pratique très vite.

Winston Ewert
la source
1
La taille d'un tableau redimensionnable est doublée à chaque remplissage; le coût moyen de redimensionnement par insertion est donc O (1).
Kevin Cline
2
@ kevincline, oui, mais le O (n) vient du fait de devoir déplacer tous les éléments après le point d'insertion. L'allocation est amortie sur O (1) fois. Ce que je veux dire, c'est que ce mouvement est encore très rapide et qu'en pratique, cela bat généralement des listes chaînées.
Winston Ewert
La raison pour laquelle les tableaux contigus sont si rapides par rapport aux listes chaînées est due à la mise en cache du processeur. Traverser une liste liée entraînera une perte de cache pour chaque élément. Pour obtenir le meilleur des deux mondes, vous devez utiliser une liste de liens déroulés .
dan_waterworth
Les tableaux redimensionnables ne copient pas toujours. Cela dépend de ce qui se passe et s'il y a quelque chose dans le chemin. Même chose pour la taille doublée, spécifique à l'implémentation. Le roll over roll over est un problème. Les listes chaînées sont généralement préférables pour les files d'attente de taille inconnue, bien que les tampons rotatifs leur donnent un avantage. Dans d'autres cas, les listes chaînées sont utiles car l'allocation ou l'extension ne vous laissera tout simplement pas avoir des éléments contigus tout le temps, vous aurez donc besoin d'un pointeur de toute façon.
Jgmjgm le
@jgmjgm, si vous insérez au milieu d'un tableau redimensionnable, son copie absolument les éléments suivants.
Winston Ewert
8

La notation Big-Oh est utilisée pour décrire le taux de croissance d'une fonction. Il est donc possible qu'un algorithme O (1) soit plus rapide, mais seulement jusqu'à un certain point (le facteur constant).

Notations communes:

O (1) - Le nombre d'itérations (vous pouvez parfois appeler cela le temps utilisateur passé par la fonction) ne dépend pas de la taille de l'entrée, mais est en fait constant.

O (n) - Le nombre d'itérations augmente dans un linéaire proportionnellement à la taille de l'entrée. Signification - si l'algorithme itère via une entrée N, 2 * N fois, il est toujours considéré comme O (n).

O (n ^ 2) (quadratique) - Le nombre d'itérations est la taille d'entrée au carré.

Yam Marcovic
la source
2
Pour ajouter un exemple à une réponse par ailleurs excellente: une méthode O (1) peut prendre 37 ans par appel, alors qu'une méthode O (n) peut prendre 16 * n microsecondes par appel. Lequel est plus vite?
Kaz Dragon
16
Je ne vois absolument pas comment cela répond à la question.
avril
7
Je comprends big-O. Cela n'aborde pas la question, à savoir des exemples spécifiques de fonctions dans lesquelles les algorithmes avec un big-O inférieur sont surperformés par ceux avec un big-O supérieur.
KyleWpppd
Lorsque vous posez la question sous la forme "Existe-t-il des exemples ...", quelqu'un va inévitablement répondre "Oui". sans en donner.
Rakslice
1
@rakslice: Peut-être. Cependant, ce site exige des explications (ou, mieux encore, des preuves) de vos déclarations. Maintenant, le meilleur moyen de prouver qu’il existe de tels exemples est d’en donner un;)
back2dos
6

Les bibliothèques de regex sont généralement implémentées pour effectuer un retour en arrière avec le temps exponentiel dans le pire des cas, plutôt que la génération DFA avec une complexité de O(nm).

Le retour en arrière naïf peut être plus performant lorsque l'entrée reste sur la voie rapide ou échoue sans qu'il soit nécessaire de revenir en arrière de manière excessive.

(Bien que cette décision ne repose pas uniquement sur les performances, elle permet également d'autoriser les références en arrière.)

dan_waterworth
la source
Je pense que c'est aussi en partie historique: l'algorithme permettant de transformer une expression régulière en DFA a été breveté au moment du développement de certains des outils précédents (sed et grep, je suppose). Bien sûr, mon professeur de compilateur n’en était pas tout à fait au courant, c’est donc un récit de troisième main.
Tikhon Jelvis
5

Un O(1)algorithme:

def constant_time_algorithm
  one_million = 1000 * 1000
  sleep(one_million) # seconds
end

Un O(n)algorithme:

def linear_time_algorithm(n)
  sleep(n) # seconds
end

Clairement, pour toute valeur de nwhere n < one_million, l' O(n)algorithme donné dans l'exemple sera plus rapide que l' O(1)algorithme.

Bien que cet exemple soit un peu facétieux, il est équivalent dans l’esprit à l’exemple suivant:

def constant_time_algorithm
  do_a_truckload_of_work_that_takes_forever_and_a_day
end

def linear_time_algorithm(n)
  i = 0
  while i < n
    i += 1
    do_a_minute_amount_of_work_that_takes_nanoseconds
  end
end

Vous devez connaître les constantes et les coefficients dans votre Oexpression, et vous devez connaître la gamme prévue de n, afin de déterminer a priori quel algorithme va finir par être plus rapide.

Sinon, vous devez comparer les deux algorithmes avec des valeurs comprises ndans la plage attendue afin de déterminer a posteriori lequel de ces algorithmes s'est avéré le plus rapide.

Yfeldblum
la source
4

Tri:

Le tri par insertion est O (n ^ 2) mais surpasse les autres algorithmes de tri O (n * log (n)) pour un petit nombre d'éléments.

C'est la raison pour laquelle la plupart des implémentations de tri utilisent une combinaison de deux algorithmes. Par exemple, utilisez le tri par fusion pour décomposer les tableaux de grande taille jusqu'à atteindre une taille définie, puis utilisez le tri par insertion pour trier les unités plus petites et les fusionner à nouveau avec le tri par fusion.

Voir Timsort l'implémentation par défaut actuelle du tri Python et Java 7 qui utilise cette technique.

OliverS
la source
3

Le Bubblesort en mémoire peut surpasser le tri rapide lorsque le programme est échangé sur le disque ou qu'il est nécessaire de lire chaque élément du disque lors de la comparaison.

Cela devrait être un exemple auquel il peut s'identifier.

utilisateur1249
la source
Les complexités citées sur quicksort et bubblesort supposent-elles un accès aléatoire à la mémoire O (1)? Si ce n’est plus le cas, n’aurions-nous pas besoin de réexaminer la complexité des shortorts?
Viktor Dahl
@ViktorDahl, le temps d'accès aux éléments ne fait pas partie de ce qui est traditionnellement mesuré dans les complexités des algorithmes de tri. "O (1)" n'est donc pas le bon choix de mots ici. Utilisez "temps constant" à la place. PHK a écrit un article il y a quelque temps sur les algorithmes de tri, sachant que certains éléments sont plus coûteux à récupérer que d'autres (mémoire virtuelle) - queue.acm.org/detail.cfm?id=1814327 - vous trouverez peut-être cela intéressant.
Je vois mon erreur maintenant. On mesure généralement le nombre de comparaisons, et bien sûr elles ne sont pas affectées par la vitesse du support de stockage. Merci également pour le lien.
Viktor Dahl
3

Les algorithmes les plus avancés supposent souvent une certaine configuration (coûteuse). Si vous ne devez l'exécuter qu'une seule fois, la méthode de la force brute vous conviendra peut-être mieux.

Par exemple: recherche binaire et une table de hachage recherche sont à la fois beaucoup plus rapide par recherche alors une recherche linéaire, mais ils vous demandent de trier la liste ou construire la table de hachage, respectivement.

Le tri vous coûtera N log (N) et la table de hachage coûtera au moins N. Maintenant, si vous effectuez des centaines ou des milliers de recherches, il s'agit toujours d'une économie amortie. Toutefois, si vous n'avez besoin que d'une ou deux recherches, il est peut-être judicieux d'effectuer une recherche linéaire et d'économiser les coûts de démarrage.

Matthew Scouten
la source
1

Le déchiffrement est souvent 0 (1). Par exemple, l'espace de clé pour DES est 2 ^ 56, le décryptage de tout message est donc une opération à temps constant. C'est juste que vous avez un facteur de 2 ^ 56, donc c'est une très grosse constante.

Zachary K
la source
Le déchiffrement d’un message n’est-il pas O ( n ), où n est proportionnel à la taille du message? Tant que vous avez la bonne clé, la taille de la clé n’entre même pas en considération; certains algorithmes ont peu ou pas de processus d’installation / d’extension de clé (DES, RSA - notez que la génération de clé peut encore être une tâche complexe, mais que cela n’a rien à voir avec une expansion de clé) alors que d’autres sont extrêmement complexes (Blowfish vient à l’esprit), mais une fois que c'est fait, le temps nécessaire pour effectuer le travail est proportionnel à la taille du message, d'où O (n).
un CVn
Vous voulez probablement dire cryptananalyse plutôt que décryptage?
gauche vers
3
Eh bien, oui, il y a un certain nombre de choses que vous pouvez prendre pour être constantes et déclarer un algorithme pour être O (1). [le tri suppose implicitement que les éléments prennent un temps constant pour comparer, par exemple, ou n'importe quel calcul avec des nombres non-bignum]
Aléatoire832
1

Différentes mises en œuvre des ensembles me viennent à l’esprit. L’un des plus naïfs est de le mettre en œuvre sur un vecteur, ce qui signifie removeaussi bien que contains, par conséquent, que addtous prennent O (N).
Une alternative consiste à l'implémenter sur un hachage général, qui mappe les hachages d'entrée sur les valeurs d'entrée. Une telle implémentation d'ensemble fonctionne avec O (1) pour add, containset remove.

Si nous supposons que N est environ 10 ou plus, alors la première mise en œuvre est probablement plus rapide. Pour trouver un élément, il suffit de comparer 10 valeurs à une.
L'autre implémentation devra démarrer toutes sortes de transformations intelligentes, ce qui peut être beaucoup plus coûteux, que de faire 10 comparaisons. Avec tous les frais généraux, vous pouvez même avoir des erreurs de cache et peu importe la rapidité de votre solution en théorie.

Cela ne signifie pas que la pire mise en œuvre à laquelle vous pouvez penser dépassera celle décente, si N est suffisamment petit. Cela signifie simplement, pour un N suffisamment petit, qu’une implémentation naïve, avec un faible encombrement et une surcharge de travail, peut nécessiter moins d’instructions et causer moins de ratés de cache qu’une implémentation qui donne la priorité à l’évolutivité et sera donc plus rapide.

Vous ne pouvez pas vraiment savoir à quelle vitesse tout est dans un scénario réel, jusqu'à ce que vous le mettiez dans un scénario et le mesuriez simplement. Les résultats sont souvent surprenants (du moins pour moi).

back2dos
la source
1

Oui, pour un N. convenablement petit, il y aura toujours un N, au-dessus duquel vous aurez toujours l'ordre suivant: O (1) <O (lg N) <O (N) <O (N log N) <O (N ^ c ) <O (c ^ N) (où O (1) <O (lg N) signifie qu’à un algorithme O (1), il faudra moins d’opérations lorsque N est convenablement grand et c est une constante fixe supérieure à 1 )

Supposons qu'un algorithme O (1) particulier prenne exactement f (N) = 10 ^ 100 opérations (un googol) et qu'un algorithme O (N) prenne exactement g (N) = 2 N + 5 opérations. L’algorithme O (N) donnera de meilleures performances jusqu’à ce que vous N soyez à peu près un googol (en fait, lorsque N> (10 ^ 100 - 5) / 2), donc si vous vous attendez à ce que N soit compris entre 1000 et un milliard, subirait une pénalité majeure en utilisant l'algorithme O (1).

Ou, pour une comparaison réaliste, supposons que vous multipliez les nombres à n chiffres. L' algorithme de Karatsuba comprend au plus 3 n ^ (lg 3) opérations (c'est-à-dire approximativement O (n ^ 1.585)), tandis que l' algorithme de Schönhage – Strassen correspond à O (N log N log log N), ce qui est un ordre plus rapide . Wikipédia:

En pratique, l'algorithme de Schönhage – Strassen commence à surpasser les anciennes méthodes telles que la multiplication de Karatsuba et Toom – Cook pour des nombres supérieurs à 2 ^ 2 ^ 15 à 2 ^ 2 ^ 17 (10 000 à 40 000 chiffres décimaux) [4] [5] [6 ]

Donc, si vous multipliez des nombres de 500 chiffres ensemble, il n’a pas de sens d’utiliser l’algorithme «plus rapide» avec de gros arguments O.

EDIT: Vous pouvez trouver déterminer f (N) comparé à g (N), en prenant la limite N-> infini de f (N) / g (N). Si la limite est 0 alors f (N) <g (N), si la limite est infinie, alors f (N)> g (N), et si la limite est une autre constante, alors f (N) ~ g (N) en termes de grande notation O.

dr jimbob
la source
1

La méthode simplex pour la programmation linéaire peut être exponentielle dans le pire des cas, tandis que les algorithmes de points intérieurs relativement nouveaux peuvent être polynomiaux.

Cependant, dans la pratique, le pire cas exponentiel pour la méthode simplex ne se présente pas: la méthode simplex est rapide et fiable, tandis que les premiers algorithmes de points intérieurs étaient beaucoup trop lents pour être compétitifs. (Il existe maintenant des algorithmes de point intérieur plus modernes qui sont compétitifs - mais la méthode simplex l'est aussi ...)

venir tempête
la source
0

L'algorithme d'Ukkonen pour la construction de suffixes est O (n log n). Il a l'avantage d'être "en ligne", c'est-à-dire que vous pouvez ajouter progressivement plus de texte.

Récemment, d'autres algorithmes plus complexes ont prétendu être plus rapides dans la pratique, en grande partie parce que leur accès mémoire a une localité plus élevée, améliorant ainsi l'utilisation de la mémoire cache du processeur et évitant les blocages du pipeline de la CPU. Voir, par exemple, cette enquête , qui affirme que 70 à 80% du temps de traitement est passé à attendre de la mémoire, et cet article décrivant l’algorithme "wotd".

Les essais de suffixes sont importants en génétique (pour l’appariement des séquences de gènes) et, dans une moindre mesure, dans la mise en œuvre des dictionnaires Scrabble.

Ed Staub
la source
0

L' algorithme est toujours le plus rapide et le plus rapide pour tout problème bien défini . Ce n'est que théoriquement purement l'algorithme (asymptotiquement) le plus rapide.

Compte tenu de toute description d'un problème P et une instance pour ce problème je , il énumère tous les algorithmes possibles A et épreuves Pr , vérifier pour chaque paire si Pr est une preuve valable que A est l'algorithme le plus rapide asymptotiquement pour P . Si elle trouve une telle preuve, il exécute alors un sur moi .

La recherche de cette paire à l’épreuve des problèmes a une complexité O (1) (pour un problème résolu P ), de sorte que vous utilisez toujours l’algorithme asymptotiquement le plus rapide pour résoudre le problème. Cependant, comme cette constante est tellement énorme dans presque tous les cas, cette méthode est totalement inutile dans la pratique.

Alex ten Brink
la source
0

De nombreux langages / frameworks utilisent une correspondance de modèle naïve pour faire correspondre des chaînes au lieu de KMP . Nous recherchons des cordes comme Tom, New York plutôt que ababaabababababaabababababab.

Lukasz Madon
la source