Le pire est le mieux.Y a-t-il un exemple ?

https://stackoverflow.com/questions/471544

19-08-2019
|

Question

Existe-t-il un algorithme largement utilisé qui présente une complexité temporelle pire que celui d'un autre algorithme connu mais c'est un mieux choix dans tous situations pratiques (pire complexité mais mieux sinon)?

Une réponse acceptable pourrait être sous la forme :

Il existe des algorithmes A et B qui ont O(N**2) et O(N) complexité du temps en conséquence, mais Ba une si grande constante qu'il n'a aucun avantage A pour les entrées moins alors un certain nombre d'atomes dans l'univers.

Exemples de points saillants des réponses :

Algorithme simplex -- le pire des cas est le temps exponentiel -- contre. algorithmes en temps polynomial connus pour les problèmes d'optimisation convexe.
Un algorithme naïf de médiane des médianes -- dans le pire des cas O(N**2) contre. algorithme O(N) connu.
Moteurs de regex de retour en arrière - exponentiel dans le pire des cas contre. Moteurs basés sur O(N) Thompson NFA.

Tous ces exemples exploitent le pire des cas vs.scénarios moyens.

Existe-t-il des exemples qui ne reposent pas sur la différence entre le pire des cas et le pire ?scénario de cas moyen ?

En rapport:

La montée du « pire, c'est mieux ».(Pour les besoins de cette question, l'expression « Pire, c'est mieux » est utilisée dans un plus étroit (à savoir - complexité temporelle algorithmique) plus sens que dans l'article)
La philosophie de conception de Python:

Le groupe ABC visait la perfection.Par exemple, ils ont utilisé des algorithmes de structure de données à base d'arbres qui se sont révélés optimaux pour les collections asymptotiquement grandes (mais qui n'étaient pas si excellentes pour les petites collections).

Cet exemple serait la réponse s'il n'existait pas d'ordinateurs capables de stocker ces grandes collections (en d'autres termes, une grande taille n'est pas assez grande dans ce cas).
Algorithme Coppersmith-Winograd pour la multiplication matricielle carrée, c'est un bon exemple (c'est le plus rapide (2008) mais il est inférieur aux pires algorithmes). Y en a-t-il d'autres ?Extrait de l'article Wikipédia :"Il n'est pas utilisé dans la pratique car il n'offre un avantage que pour les matrices si grandes qu'elles ne peuvent pas être traitées par du matériel moderne (Robinson 2005)."

La solution 5

Coppersmith & # 8211; Algorithme Winograd pour la multiplication de matrices carrées. Sa complexité temporelle est O (n ^2.376) vs. O (n ³) d'un algorithme de multiplication naïf ou vs. O (n ^2,807) pour algorithme de Strassen .

Extrait de l'article de Wikipédia:

Cependant, contrairement aux Strassen algorithme, il n'est pas utilisé en pratique car il ne procure qu'un avantage pour les matrices si grandes qu'ils ne peuvent pas être traité par du matériel moderne (Robinson 2005).

Autres conseils

quick-sort présente la complexité temporelle la plus défavorable de O (N ^ 2), mais elle l'est généralement considéré comme meilleur que les autres algorithmes de tri qui ont dans le pire des cas une complexité temporelle de O (N log n).

Simplex est un algorithme qui présente une complexité temporelle exponentielle dans le pire des cas, mais dans tous les cas réels. c'est polynomial. Des algorithmes polynomiaux probablement pour la programmation linéaire existent , mais ils sont très compliqués et ont généralement de grandes constantes.

& "Pire c'est mieux" & "; peut être vu aussi dans les langages, par exemple les idées derrière Perl, Python, Ruby, Php même C # ou Java, ou n’importe quel langage qui n’est ni assembleur ni C (C ++ pourrait s’adapter ici ou non).

En gros, il existe toujours un & "parfait &"; solution, mais il est souvent préférable d’utiliser un " pire " outil / algorithme / langage pour obtenir des résultats plus rapidement et avec moins de douleur. C’est la raison pour laquelle les gens utilisent ces langages de niveau supérieur, bien qu’ils soient & «Pires &»; du point de vue idéal du langage informatique, et sont plutôt plus humains.

L'intégration de Monte Carlo est une méthode probabiliste de calcul des intégrales définies sans garantie de restitution. bonne réponse. Cependant, dans des situations réelles, il fournit une réponse précise beaucoup plus rapidement que des méthodes prouvées comme correctes.

Cette instruction peut être appliquée à presque tous les algorithmes parallèles . La raison pour laquelle ils n’ont pas fait l’objet de très nombreuses recherches aux débuts de l’informatique est qu’ils sont en fait plus lents que leurs homologues séquentiels bien connus en termes de complexité asymptotique, de constants facteurs de petite taille, pour un seul fil d’exécution (think uniprocessor). > n , ou les deux. Toutefois, dans le contexte des plates-formes informatiques actuelles et futures, un algorithme qui peut utiliser quelques éléments de traitement (pensez multicœurs), quelques centaines (pensez GPU) ou quelques milliers (pensez supercalculateur) dépassera les pantalons de la version séquentielle. en horloge murale, même si la durée / énergie totale dépensée par tous les processeurs est beaucoup plus grande pour la version parallèle.

Les techniques de calcul, d’algorithmes de graphes et d’algèbre linéaire peuvent être accélérées en termes de temps de travail en prenant en charge le coût d’un peu plus de tenue de livres, de communication et de temps d’exécution afin de paralléliser.

Il s'agit souvent d'un algorithme (tel que quicksort ) pouvant être facilement parallélisé ou randomisé sera choisi par rapport à des algorithmes concurrents dépourvus de ces qualités. En outre, il est fréquent qu’une solution approximative à un problème soit acceptable lorsqu'un algorithme exact Cela produirait des temps d’exécution exponentiels, comme dans le problème de voyageur de commerce .

Cet exemple serait la solution s'il n'y avait pas d'ordinateurs capables de stocker ces grandes collections.

Vraisemblablement, la taille de la collection était de 641 Ko.

Lorsque nous travaillions dans le groupe informatique technique pour BAE SYSTEMS, qui s’occupait du code structurel et aérodynamique de divers aéronefs, nous avions une base de code remontant au moins 25 ans (et un tiers du personnel était là depuis si longtemps).

De nombreux algorithmes ont été optimisés pour les performances sur un ordinateur central 16 bits, plutôt que pour leur évolutivité. Ces optimisations étaient tout à fait appropriées pour le matériel des années 1970, mais ont mal fonctionné avec des jeux de données plus volumineux sur les systèmes 32 et 64 bits qui l'ont remplacé. Si vous choisissez quelque chose de moins évolutif, qui fonctionne mieux sur le matériel sur lequel vous travaillez actuellement, sachez qu'il s'agit d'une optimisation et que cela pourrait ne pas s'appliquer dans le futur. Au moment où ces routines des années 1970 ont été écrites, la taille des données que nous y avons introduites dans les années 2000 n'était pas pratique. Malheureusement, essayer d'extraire de ces codes un algorithme clair qui pourrait ensuite être mis en œuvre pour s'adapter au matériel moderne n'était pas anodin.

À part l'ébullition des océans, ce qui compte comme "toutes les situations pratiques" est souvent une variable dépendante du temps.

Un exemple provient de la géométrie de calcul. La la triangulation des polygones utilise le pire cas de l'algorithme O (N) en raison de Chazelle , mais il n’est presque jamais mis en oeuvre dans la pratique en raison de la rigueur de la mise en œuvre et de son énorme constante.

Pas tout à fait à la marque, mais les expressions régulières basées sur le retour arrière ont un pire cas exponentiel par rapport à O (N) pour les expressions régulières basées sur DFA, pourtant les expressions régulières basées sur le retour arrière sont presque toujours utilisées plutôt que celles basées sur DFA.

EDIT: (JFS)

La correspondance des expressions rationnelles peut être simple et rapide (mais est lente en Java, Perl, PHP , Python, Ruby, ...) :

Le pouvoir que les références arrière ajoutent vient au prix fort: dans le pire cas, les implémentations les plus connues requièrent des algorithmes de recherche exponentiels.

Moteurs d'expressions réguliers :

Cette méthode (DFA) est vraiment plus efficace et peut même être adaptée pour permettre la capture et la correspondance non gourmande , mais elle présente également des inconvénients importants:

Les vérifications sont impossibles
Les références arrières sont également impossibles
La pré-compilation Regex est plus longue et prend plus de mémoire

Du côté positif, en plus d’éviter les temps d’exécution exponentiels dans le cas le plus défavorable, les approches DFA évitent l’utilisation d’une pile dans le cas le plus défavorable qui soit linéaire dans la taille des données en entrée.

[3]:

Il existe un algorithme temporel polynomial pour déterminer la primalité, mais en pratique, il est toujours plus rapide d’utiliser un algorithme temporel exponentiel ou d’effectuer suffisamment de calculs probabilistes pour avoir une certitude suffisante.

Le type Radix a une complexité temporelle O (n) pour les entrées de longueur fixe, mais le tri rapide est utilisé plus souvent, malgré la pire durée d'exécution, car la surcharge par élément du type Radix est généralement beaucoup plus élevée.

Ok, envisagez de résoudre le problème du vendeur itinérant. La solution idéale UNIQUEMENT consiste à tester tous les itinéraires possibles. Cependant, cela devient impossible avec notre matériel et les délais lorsque N augmente. Nous avons donc pensé à de nombreuses heuristiques.

Ce qui nous amène à la réponse à votre question. Les heuristiques (pires) sont meilleures que la force brute pour les problèmes NP-complets. Ceci décrit la situation dans laquelle & "Worse is Better &"; est toujours vrai.

Lors du calcul de la médiane d'un groupe de nombres, vous pouvez utiliser un algorithme très similaire à quicksort. Vous divisez autour d'un nombre, et tous les plus grands vont d'un côté, et tous les plus petits vont de l'autre côté. Ensuite, vous jetez un côté et calculez de manière récursive la médiane du plus grand côté. Cela prend O (n ^ 2) dans le pire des cas, mais est assez rapide (O (n) avec une constante faible) dans le cas moyen.

Vous pouvez obtenir des performances garanties dans le pire des cas (O), avec une constante d'environ 40. C'est ce qu'on appelle le algorithme de la médiane des médianes . En pratique, vous ne l'utiliseriez jamais.

Si je comprends bien la question, vous demandez des algorithmes théoriquement meilleurs mais pratiquement pires dans toutes les situations. Par conséquent, on ne s'attendrait pas à ce qu'ils soient réellement utilisés, sauf par erreur.

Un mémoization universel est un exemple possible. Théoriquement, tous les appels de fonction déterministes devraient être mémorisés pour toutes les entrées possibles. De cette façon, les calculs complexes pourraient être remplacés par de simples recherches dans des tableaux. Pour un large éventail de problèmes, cette technique négocie de manière productive le temps nécessaire à l’espace de stockage. Mais supposons qu'il y ait un répertoire central des résultats de toutes les entrées possibles pour toutes les fonctions possibles utilisées par tous les ordinateurs de l'humanité. La première fois que quelqu'un a fait un calcul, ce serait la dernière fois. Tous les essais ultérieurs donneraient lieu à une recherche dans une table.

Mais je peux penser à plusieurs raisons pour ne pas le faire:

L'espace mémoire requis pour stocker tous les résultats serait probablement trop important. Il semble probable que le nombre de bits nécessaires dépasserait le nombre de particules dans l'univers. (Mais même la tâche d'estimer ce nombre est décourageante.)
Il serait difficile de construire un algorithme efficace pour mémoriser cet énorme espace problématique.
Le coût de la communication avec le référentiel central dépasserait probablement les avantages lorsque le nombre de clients augmente.

Je suis sûr que vous pouvez penser à d'autres problèmes.

En fait, ce type de compromis temps / espace est incroyablement courant dans la pratique. Idéalement, toutes les données seraient stockées dans le cache L1, mais en raison de limitations de taille, vous devez toujours placer certaines données sur disque ou sur une bande (horreur!). Les technologies de pointe réduisent en partie les inconvénients de ces compromis, mais comme je l’ai suggéré plus haut, il existe des limites.

En réponse au commentaire de J.F. Sebastian:

Supposons qu'au lieu d'un référentiel de mémorisation universel, nous considérons un référentiel factoriel. Et il ne tiendra pas les résultats pour toutes les entrées possibles. Au lieu de cela, il se limitera aux résultats de 1 à N! Il est maintenant facile de voir que tout ordinateur utilisant des factorielles bénéficierait de la recherche du résultat plutôt que du calcul. Même pour calculer (N+1)! la recherche constituerait un gain énorme, car ce calcul ramènerait à N!(N+1).

Maintenant, pour améliorer & "mieux &"; algorithme pire, nous pourrions soit augmenter N, soit augmenter le nombre d’ordinateurs utilisant le référentiel.

Mais je ne comprends probablement pas la subtilité de la question. Comme je le pense, je continue à proposer des exemples qui vont bien jusqu'à ce qu'ils ne le fassent pas.

Mergesort versus Quicksort

Le tri rapide a une complexité temporelle moyenne de O ( n journal n ). Il peut trier les tableaux en place, c’est-à-dire une complexité spatiale de O (1).

Le type de fusion

a également une complexité temporelle moyenne égale à O ( n journal n ), mais sa complexité d'espace est beaucoup pire : # 920; ( n ). (il existe un cas particulier pour les listes chaînées)

En raison du pire cas de tri rapide, la complexité temporelle est & # 920; (n ^ 2) (tous les éléments tombent du même côté de chaque pivot), et le cas le plus défavorable de mergesort est O ( n log n ), mergesort est le choix par défaut des développeurs de bibliothèques.

Dans ce cas, je pense que la prévisibilité de la complexité temporelle du cas le plus défavorable de mergesort l'emporte sur les besoins en mémoire beaucoup plus faibles de quicksorts.

Étant donné qu'il est possible de réduire considérablement la probabilité du pire cas de complexité temporelle du tri rapide (par exemple, en sélectionnant au hasard le pivot), je pense que l'on pourrait affirmer que le mergesort est pire dans tous les cas, sauf le cas pathologique du tri rapide.

J'ai toujours compris que le terme "pire, c'est mieux" est lié à des problèmes avec des solutions correctes très complexes lorsqu'il existe une solution approximative (ou suffisante) relativement facile à comprendre.

Cela facilite la conception, la production et la maintenance.

Il existe un algorithme O (n) pour sélectionner le k-ème plus grand élément d'un ensemble non trié, mais il est rarement utilisé à la place du tri, qui est bien sûr O (n logn).

Tri par insertion malgré O(n²) la complexité est plus rapide pour les petites collections (n < 10) que pour tout autre algorithme de tri.C'est parce que la boucle imbriquée est petite et s'exécute rapidement.De nombreuses bibliothèques (y compris STL) qui implémentent une méthode de tri l'utilisent en fait pour de petits sous-ensembles de données afin d'accélérer les choses.

L'intégration de Monte Carlo a déjà été suggérée, mais un exemple plus spécifique est la tarification de Monte Carlo en finance. Ici, la méthode est beaucoup plus facile à coder et peut faire plus de choses que d’autres MAIS elle est beaucoup plus lente que disons, différence finie.

il n’est pas pratique de faire des algorithmes en différences finies à 20 dimensions, mais l’exécution de la tarification en 20 dimensions est facile à configurer.

Le type Spaghetti est meilleur que tout autre algorithme de tri en ce qu'il est O (n ) pour configurer, O (1) pour exécuter et O (n) pour extraire les données triées. Il accomplit tout cela dans la complexité de l'espace O (n). (Performance globale: O (n) dans le temps et dans l’espace.) Pourtant, pour une raison étrange (évidente), personne ne l’utilise pour rien du tout, préférant les algorithmes très inférieurs de O (nlogn) et leurs semblables.

Approfondissement itératif

Par rapport à une recherche triviale en profondeur d'abord augmentée de la élagage en version bêta une approfondissement itératif utilisé conjointement avec un ordre de branche faible (ou inexistant) heuristique entraînerait beaucoup plus de nœuds en cours d'analyse. Cependant, lorsqu'une bonne heuristique de classement des branches est utilisée, une partie importante de l'arbre est éliminée en raison de l'effet amélioré de l'élagage alpha-bêta. Un deuxième avantage, non lié à la complexité du temps ou de l'espace, est qu'une estimation de la solution par rapport au domaine du problème est établie tôt et que cette dernière est affinée au fur et à mesure que la recherche avance. C’est ce deuxième avantage qui le rend si attrayant dans de nombreux domaines problématiques.

Quick-sort has worst case time complexity of O(N^2)! 
It is considered better than other sorting algorithms 
like mergesort heapsort etc. which have O(N log n) time complexity 
in the worst case.
The reason may be the 
1.in place sorting 
2.stability, 
3.very less amount of code involved.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow