Le pire, c'est mieux. Est-il un exemple?

Question

Est-il largement utilisé l'algorithme qui a le temps de la complexité pire que celui d'un autre algorithme connu, mais il est un meilleur choix dans toutes les situations pratiques (le pire de complexité, mais mieux sinon)?

Une réponse acceptable pourrait être dans un formulaire:

Il existe des algorithmes A et Bque ont O(N**2) et O(N)du temps la complexité en conséquence, mais B a une telle grande constant qu'il n'a pas de avantages par rapport A pour les entrées moins ensuite, un certain nombre d'atomes dans l' De l'univers.

Exemples saillants des réponses:

• Algorithme du simplexe -- le pire des cas est temps exponentiel -- vs connu polynomiale en temps des algorithmes pour les problèmes d'optimisation convexe.

• Un naïf médian des médianes algorithme -- pire des cas en O(N**2) vs connu algorithme O(N).

• Mandature regex moteurs-pire-cas exponentiel vs O(N) Thompson ADN à base de moteurs.

Tous ces exemples exploiter le pire des cas vs moyenne des scénarios.

Sont là des exemples qui ne reposent pas sur la différence entre le pire des cas vs moyenne des scénarios?

---

Connexes:

• La Montée de la `Pire, c'est Mieux". (Pour les fins de cette question, le "Pire, Mieux c'est" la phrase est utilisée dans une plus étroite (à savoir -- algorithmique temps-la complexité) de sens que dans l'article)

• Python Philosophie de Conception:

  Le groupe ABC s'est efforcé de la perfection. Par exemple, ils ont utilisé de l'arborescence de base de données la structure des algorithmes qui ont été prouvés pour être optimale, pour asymptotiquement grand collections (mais ne sont pas pour les petites collections).

  Cet exemple serait la réponse si il n'y avait pas d'ordinateurs capables de stocker ces grandes collections (en d'autres termes large n'est pas assez grand dans ce cas).

• Chaudronnerie–algorithme de Winograd pour le carré de la matrice de la multiplication est un bon exemple (c'est le plus rapide (2008), mais elle est inférieure à la pire des algorithmes). Tout les autres? À partir de l'article de wikipédia: "Elle n'est pas utilisée en pratique, car il fournit seulement un avantage pour les matrices si grande qu'ils ne peuvent pas être traitées par du matériel moderne (Robinson, 2005)."

Answer 1

tri rapide a pire des cas, la complexité temporelle de O(N^2), mais il est généralement considéré comme meilleur que les autres algorithmes de tri qui ont O(N log n) complexité temporelle dans le pire des cas.

Answer 2

Simplex est un algorithme qui a exponentielle de la complexité temporelle dans le pire des cas, mais pour tout réel cas, il est polynomiale. Probablement polynôme algorithmes de programmation linéaire existent mais elles sont très compliquées et ont généralement de grandes constantes.

Answer 3

Monte-Carlo de l'intégration est une méthode probabiliste de calcul des intégrales, qui n'a aucune garantie de retour de la réponse correcte. Pourtant, dans des situations du monde réel, il renvoie une réponse précise est bien plus rapide que prouvable des méthodes correctes.

Answer 4

"Le pire, c'est Mieux" peut être vu dans les langues, par exemple, les idées derrière Perl, Python, Ruby, Php, même C# ou Java, ou quelle que soit la langue qui n'est pas de l'assembleur ou C (C++ peut s'appliquer ici, ou pas).

Fondamentalement, il y a toujours un "parfait" solution, mais de nombreuses fois il est mieux d'utiliser un "pire" outil/algorithme/langue pour obtenir des résultats plus rapidement, et avec moins de douleur. C'est pourquoi les gens utilisent ces langues, même si elles sont "pires" de l'idéal de l'ordinateur de langue point de vue, et au lieu de cela plus humaines axée sur les résultats.

Answer 5

Chaudronnerie–algorithme de Winograd pour le carré de la matrice de multiplication. Son temps de la complexité est O(n^2.376) contre O(n³) d'un naïfs algorithme de multiplication ou vs O(n^2.807) pour l' algorithme de Strassen.

À partir de l'article de wikipédia:

Cependant, contrairement à l'Strassen algorithme, il n'est pas utilisé dans la pratique parce qu'il ne donne un avantage pour les matrices si grande qu'ils ne peuvent pas être traitées par du matériel moderne (Robinson, 2005).