Pourquoi étudier la théorie de la complexité?

Question

Je suis un amateur dans l'étude des algorithmes. Pendant un moment, j'ai eu une question brûlante, pourquoi étudions-nous la théorie de la complexité en informatique? La raison pour laquelle je demande est que des algorithmes avec une meilleure complexité asymptotique ne sont pas toujours plus rapides à des fins pratiques, ils peuvent en fait être absurdes. Pourquoi ne pas développer une théorie qui convient mieux aux besoins pratiques de la recherche scientifique et de l'industrie?

À titre d'exemple, il est connu que le développement d'un algorithme pour déterminer un jeu d'échecs parfait peut être fait dans $ o (1) $ , comme le nombre de légumes Les jeux d'échecs sur une grille de 8 × 8 sont délimités d'en haut. Cependant, j'ai entendu dire que cet algorithme prendrait plus de temps que l'âge de l'univers pour terminer. Cela pose la question, pourquoi la théorie de la complexité? Il me semble que le domaine est fondamentalement imparfait et les informaticiens devraient utiliser une meilleure approche pour l'étude des algorithmes.

(Remarque: mes excuses sincères aux chercheurs sur le terrain. ☻)

Answer 1

Ce n'est pas une question simple et vous ne devriez pas vous attendre à une réponse simple. Il existe une gamme de questions similaires dans cet espace: pourquoi étudions-t-on le temps de fonctionnement asymptotique? Pourquoi utilisons-nous une analyse de temps d'exécution asymptotique pour analyser les algorithmes? Pourquoi étudions-nous la théorie de la complexité? Chacun de ceux-ci a plusieurs réponses; Il n'y a pas qu'une seule raison pour laquelle nous le faisons et que différentes personnes peuvent avoir des raisons différentes.

L'analyse de temps d'exécution asymptotique présente des avantages et des inconvénients. Vous avez identifié avec précision l'un des inconvénients: une bonne durée de fonctionnement asymptotique ne garantit pas une bonne heure de fonctionnement dans la pratique. Mais si vous vous concentrez sur un seul avantage ou un désavantage, vous n'allez pas obtenir l'image complète des forces et des faiblesses de ce style d'analyse. Certains des avantages sont que l'analyse est relativement traitable, elle n'est pas spécifique à une architecture particulière, elle fournit des informations utiles sur l'évolutivité et au moins une partie du temps qu'il a une puissance prédictive utile pour identifier les goulots d'étranglement algorithmiques. Par exemple, la différence entre une $ O (n ^ 2) $ algorithme de temps et une $ o (n \ log n ) $ L'algorithme de temps peut souvent être significatif, même si nous ignorons les facteurs constants. Certains des inconvénients sont que des facteurs constants peuvent être importants, les effets de la hiérarchie du cache et de la mémoire peuvent être très importants mais sont ignorés par l'analyse de temps d'exécution asymptotique, et (comme toute métrique) optimisant uniquement pour le temps de fonctionnement asymptotique peut entraîner des résultats absurdes de peu pratiques. utilitaire (voir algorithmes galactiques et Law Goodhart ).

Je pense qu'il est également utile d'examiner l'alternative. Je vous encourage à explorer l'alternative à l'analyse de temps de fonctionnement asymptotique et à travailler à travers ce que vous proposeriez dans sa place. Si vous n'essayez pas de trouver une proposition concrète, il est facile de supposer que cela ne peut pas être si difficile de trouver quelque chose de mieux ... mais lorsque vous êtes obligé de vous engager à quelque chose de spécifique, vous pourriez découvrir que c'est plus difficile que prévu. Par exemple, je vous encourage à vous familiariser avec l'analyse de Knuth de l'algorithme de temps d'exécution sur Mix dans son Série TAOCP. Là, il effectue une analyse de temps de fonctionnement concrète, sans asymptotique, en tenant compte des facteurs constants. Si vous vous forcez à travailler dans les détails de cela, vous découvrirez rapidement les inconvénients de cela: c'est super fastidieux, très spécifique à une architecture informatique particulière, et souvent pas beaucoup plus illuminante.

Nous pourrions également discuter de chacun des autres sujets - par exemple, pourquoi ou pourquoi ne pas étudier la théorie de la complexité - et vous constateriez qu'elles aussi ont des nuances.

Je tiens également à mettre en évidence que la communauté théorie et algorithme est large, avec une gamme de styles de travail différents. Vous semblez y remue tout ensemble en une seule pile, mais il y a un spectre de travail: une partie de celle-ci est super théorique et loin de la pratique, dont certaines sont très pratiques et motivées par des problèmes concrets et peuvent avoir un impact immédiat et Il existe une gamme de travaux à différents points entre ces extrêmes. Je pense qu'il est important de comprendre qu'il existe des travaux dans la communauté théorique qui revêt une grande pertinence pratique ou a eu un impact majeur, tout comme il y a du travail qui est beaucoup plus théorique et non motivé par un impact à court terme.

Comme vous avez demandé des cadres théoriques axés sur les besoins de la réunion de la réunion, vous pourriez également être intéressé par le Word Ram modèle, algorithmes de cache-incivieux , et le Mémoire externe parallèle modèle.

Je vous encourage fortement à lire les ressources suivantes, car elles sont étroitement liées à votre question: Pourquoi le temps polynomial est appelé " efficace "? , Expliquer la pertinence de la complexité asymptotique d'algorithmes à la pratique de la conception d'algorithmes , Justification de négligence de facteurs constants dans Big O .