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

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 ² ) é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?

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.

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.

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).

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.

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.

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.

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é.

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.)

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.

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.

L' algorithme d' unification utilisé en pratique est exponentiel dans le pire des cas, pour certaines entrées pathologiques.

Il existe un algorithme d'unification polynomiale , mais il est trop lent en pratique.

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.

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.

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.

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).

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.

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 ...)

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.

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.

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.