Avez-vous appliqué la théorie de la complexité informatique dans la vie réelle?

Question

Je suis un cours de complexité informatique et j’ai eu jusqu’à présent l’impression qu’il ne serait pas très utile pour un développeur.

Je me trompe peut-être, mais si vous vous êtes déjà engagé dans cette voie, pourriez-vous donner un exemple de la manière dont la théorie de la complexité vous a aidé dans votre travail? Des tonnes de mercis.

Answer 1

O (1): code simple sans boucles. Coule juste à travers. Les recherches dans une table de recherche sont également O (1).

O (log (n)): algorithmes optimisés efficacement. Exemple: algorithmes d'arborescence binaire et recherche binaire. Habituellement, ça ne fait pas mal. Vous avez de la chance si vous avez un tel algorithme sous la main.

O (n): une seule boucle sur des données. Fait mal pour très grand n.

O (n * log (n)): un algorithme qui fait une sorte de stratégie de division et de conquête. Fait mal pour le grand n. Exemple typique: tri par fusion

O (n * n): une boucle imbriquée de quelque sorte. Fait mal même avec petit n. Commun avec les calculs matriciels naïfs. Vous voulez éviter ce type d'algorithme si vous le pouvez.

O (n ^ x pour x > 2): une mauvaise construction avec plusieurs boucles imbriquées. Fait mal pour très petit n.

O (x ^ n, n! et pire): algorithmes bizarres (et souvent récursifs) que vous ne voulez pas avoir dans le code de production, sauf dans des cas très contrôlés, pour très petit n et s'il n'y a pas de meilleure alternative . Le temps de calcul peut exploser avec n = n + 1.

Abaisser votre algorithme d'une classe de complexité supérieure peut le faire voler à la volée. Pensez à la transformation de Fourier qui a un algorithme O (n * n) qui était inutilisable avec le matériel des années 1960, sauf dans de rares cas. Ensuite, Cooley et Tukey ont procédé à des réductions intelligentes de la complexité en réutilisant les valeurs déjà calculées. Cela a conduit à l'introduction généralisée de la FFT dans le traitement du signal. Et au final, c’est aussi pourquoi Steve Jobs a fait fortune avec l’iPod.

Exemple simple: les programmeurs Naive C écrivent ce type de boucle:

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

C'est un algorithme O (n * n) en raison de l'implémentation de strlen (). Les boucles de nidification conduisent à la multiplication des complexités à l'intérieur du big-O. O (n) à l'intérieur de O (n) donne O (n * n). O (n ^ 3) à l'intérieur de O (n) donne O (n ^ 4). Dans l'exemple, le précalcul de la longueur de la chaîne transformera immédiatement la boucle en O (n). Joel a également écrit à ce sujet.

Pourtant, la classe de complexité n’est pas tout. Vous devez garder un oeil sur la taille de n. Retravailler un algorithme O (n * log (n)) sur O (n) ne vous aidera pas si le nombre d'instructions (désormais linéaires) augmente énormément en raison de la retouche. Et si n est petit de toute façon, l’optimisation ne donnera pas beaucoup plus, aussi.

Answer 2

S'il est vrai que l'on peut aller très loin dans le développement logiciel sans la moindre compréhension de la complexité algorithmique. Je trouve que j'utilise ma connaissance de la complexité tout le temps; cependant, à ce stade, c'est souvent sans s'en rendre compte. En tant que développeur de logiciels, l'apprentissage de la complexité vous donne un moyen de comparer des algorithmes non similaires qui font la même chose (les algorithmes de tri sont l'exemple classique, mais la plupart des gens n'écrivent pas leurs propres tris). La chose la plus utile que cela vous donne est un moyen de décrire rapidement un algorithme.

Par exemple, considérons SQL. SQL est utilisé chaque jour par un très grand nombre de programmeurs. Si vous voyez la requête suivante, votre compréhension de la requête est très différente si vous avez étudié la complexité.

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

Si vous avez étudié la complexité, vous comprendrez si quelqu'un dit que c'est O (n ^ 2) pour un certain SGBD. Sans la théorie de la complexité, la personne devrait expliquer les analyses de table, etc. Si nous ajoutons un index à la table Order

CREATE INDEX ORDER_USERID ON Order(UserId)

La requête ci-dessus pourrait alors être O (n log n), ce qui ferait une énorme différence pour une base de données volumineuse, mais pour une petite base, ce n'est rien du tout.

On pourrait soutenir que la théorie de la complexité n’est pas nécessaire pour comprendre le fonctionnement des bases de données. C’est exact, mais la théorie de la complexité fournit un langage permettant de réfléchir aux algorithmes travaillant sur des données et de les utiliser.

Answer 3

Pour la plupart des types de travaux de programmation, la partie théorique et les preuves ne sont peut-être pas utiles en elles-mêmes, mais essaient simplement de vous donner l'intuition de pouvoir dire immédiatement que cet algorithme est O (n ^ 2) nous ne pouvons donc pas l’exécuter sur ces millions de points de données ". Même dans le traitement le plus élémentaire de grandes quantités de données, vous rencontrez ce problème.

Penser rapidement la théorie de la complexité a été important pour moi dans le traitement des données d’entreprise, les SIG, la programmation graphique et la compréhension des algorithmes en général. C’est l’une des leçons les plus utiles que vous puissiez tirer des études de CS par rapport à ce que vous étudieriez normalement vous-même autrement.

Answer 4

Les ordinateurs ne sont pas intelligents, ils feront tout ce que vous leur demandez. Les compilateurs peuvent optimiser un peu le code pour vous, mais ils ne peuvent pas optimiser les algorithmes. Le cerveau humain fonctionne différemment et c'est pourquoi vous devez comprendre le Big O. Pensez à calculer les nombres de Fibonacci. Nous savons tous que F (n) = F (n-1) + F (n-2), et à partir de 1,1, vous pouvez facilement calculer les nombres suivants sans trop d'effort, en temps linéaire. Mais si vous dites à l'ordinateur de le calculer avec cette formule (de manière récursive), cela ne sera pas linéaire (du moins, dans les langages impératifs). En quelque sorte, notre algorithme optimisé pour le cerveau, mais le compilateur ne peut pas faire cela. Vous devez donc travailler sur l'algorithme pour le rendre meilleur.

Et ensuite, vous avez besoin de formation, de repérage des optimisations cérébrales qui paraissent si évidentes, de voir quand le code peut être inefficace, de connaître les schémas de mauvais et de bons algorithmes (en termes de complexité de calcul), etc. Fondamentalement, ces cours ont plusieurs objectifs:

• comprendre les modèles d’exécution et les structures de données et leur effet sur le temps qu’il faut à votre programme;
• entraînez votre esprit à repérer les problèmes potentiels de l'algorithme, alors que cela pourrait être inefficace pour de grands ensembles de données. Ou comprendre les résultats du profilage;
• apprendre des moyens bien connus d'améliorer les algorithmes en réduisant leur complexité de calcul;
• préparez-vous à passer une interview dans une entreprise cool:)

Answer 5

C'est extrêmement important. Si vous ne comprenez pas comment estimer et calculer la durée d'exécution de vos algorithmes, vous finirez par écrire du code plutôt lent. Je pense tout le temps à la complexité de calcul lors de l'écriture d'algorithmes. C’est quelque chose qui devrait toujours vous préoccuper lors de la programmation.

Cela est particulièrement vrai dans de nombreux cas car, même si votre application fonctionne correctement sur votre ordinateur de bureau avec un petit ensemble de données de test, il est important de comprendre à quelle vitesse votre application réagira une fois que vous l'utiliserez, et des centaines de des milliers de personnes l'utilisant.

Answer 6

Oui, j'utilise fréquemment la notation Big-O ou plutôt les processus de pensée qui la sous-tendent, pas la notation elle-même. En grande partie parce que si peu de développeurs de l'organisation que je fréquente le comprennent bien. Je ne veux pas manquer de respect à ces gens, mais d’après mon expérience, la connaissance de ce genre de choses est l’une de ces choses qui "trient les hommes des garçons".

Je me demande s’il s’agit d’une de ces questions qui ne peut recevoir que "oui". réponses? Il me semble que le groupe de personnes qui comprend la complexité informatique est à peu près équivalent au groupe de personnes qui pensent que c'est important. Ainsi, quiconque pourrait répondre non ne comprend peut-être pas la question et passe donc directement à la question suivante plutôt que de faire une pause pour répondre. Juste une pensée ;-)

Answer 7

Il y a des moments où vous devrez faire face à des problèmes nécessitant une réflexion. Il existe de nombreux problèmes du monde réel qui nécessitent la manipulation d'un grand ensemble de données ...

Exemples:

• Application Maps ... comme Google Maps - comment traiteriez-vous les données de lignes de route dans le monde entier et les dessiniez? et vous devez les dessiner rapidement!
• Application logistique ... pensez à un vendeur itinérant sous stéroïdes
• L'exploration de données ... toutes les grandes entreprises en ont besoin. Comment exploiter une base de données contenant plus de 100 tables et plus de 10 lignes et obtenir des résultats utiles avant que les tendances ne deviennent obsolètes?

Suivre un cours de complexité informatique vous aidera à analyser et à choisir / créer des algorithmes efficaces pour de tels scénarios.

Croyez-moi, quelque chose d'aussi simple que de réduire un coefficient, disons de T (3n) à T (2n), peut faire d'énormes différences lorsque le paramètre "n" se mesure en jours sinon en mois.

Answer 8

Il y a beaucoup de bons conseils ici, et je suis sûr que la plupart des programmeurs ont utilisé leur connaissance de la complexité de temps en temps.

Cependant, je dois dire que la compréhension de la complexité informatique revêt une importance extrême dans le domaine des jeux! Oui, vous avez entendu dire que "inutile". est le genre de choses que la programmation de jeux vit.

Je parierais que très peu de professionnels s’intéressent probablement autant au Big-O qu'aux programmeurs de jeux.

Answer 9

J'utilise régulièrement des calculs de complexité, principalement parce que je travaille dans le domaine géospatial avec des jeux de données très volumineux, par exemple. processus impliquant des millions et parfois des milliards de coordonnées cartésiennes. Une fois que vous commencez à vous attaquer à des problèmes multidimensionnels, la complexité peut devenir un réel problème, car les algorithmes gloutons qui seraient O (n) dans une dimension sautent soudainement vers O (n ^ 3) en trois dimensions et il ne faut pas beaucoup de données pour créer un goulot d'étranglement sérieux. Comme je l'ai mentionné dans une publication similaire , vous voyez également la grosse notation O devenir lourde lorsque vous commencez à traiter avec des groupes d'objets complexes de taille variable. L’ordre de complexité peut également dépendre beaucoup des données, les cas types fonctionnant bien mieux que les cas généraux bien ad algorithmes hoc .

Cela vaut également la peine de tester vos algorithmes sous un profileur pour voir si ce que vous avez conçu correspond à ce que vous avez réalisé. Je trouve que la plupart des goulots d'étranglement sont résolus bien mieux avec un ajustement d'algorithme qu'une vitesse de processeur améliorée pour toutes les raisons évidentes.

Pour en savoir plus sur les algorithmes généraux et leur complexité, j'ai trouvé le le travail de Sedgewicks , à la fois informatif et accessible. Pour les algorithmes spatiaux, le livre O'Rourkes sur la géométrie algorithmique est excellent.

Answer 10

Dans votre vie normale, et non à proximité d'un ordinateur, vous devez appliquer les concepts de complexité et de traitement parallèle. Cela vous permettra d'être plus efficace. Cohérence du cache. Ce genre de chose.

Answer 11

Oui, ma connaissance des algorithmes de tri s’est révélée utile un jour où j’ai dû trier une pile d’examens. J'ai utilisé le tri par fusion (mais pas quicksort ou heapsort). Lors de la programmation, je n’utilise que la routine de tri proposée par la bibliothèque. (Je n'ai pas encore eu à trier une très grande quantité de données.)

J'utilise tout le temps la théorie de la complexité dans la programmation, principalement pour décider des structures de données à utiliser, mais également pour décider si ou quand trier les choses, et pour de nombreuses autres décisions.

Answer 12

" oui " et " non "

oui ) J'utilise fréquemment la la grande notation O lorsque développer et implémenter des algorithmes. Par exemple. lorsque vous devez gérer 10 ^ 3 éléments et que la complexité du premier algorithme est O (n log (n)) et du second O (n ^ 3), vous pouvez simplement dire que le premier algorithme est presque temps réel, tandis que le second requiert calculs considérables.

Parfois, les connaissances sur les classes de complexité de NP peuvent être utiles. Cela peut vous aider à réaliser que vous pouvez cesser de penser à l’invention d’un algorithme efficace lorsqu’un problème NP-complet peut être réduit au problème auquel vous songez.

non ) Ce que j'ai décrit ci-dessus ne représente qu'une petite partie de la théorie de la complexité. En conséquence, il est difficile de dire que je l'utilise, j'en utilise une partie mineure-mineure.

Je dois admettre qu'il existe de nombreux projets de développement de logiciels qui ne concernent ni le développement d'algorithmes ni leur utilisation de manière sophistiquée. Dans de tels cas, la théorie de la complexité est inutile. Les utilisateurs ordinaires d’algorithmes utilisent fréquemment les mots «rapide» et «lent», «x secondes», etc.

Answer 13

@Martin: Pouvez-vous préciser le processus de pensée qui le sous-tend?

cela n’est peut-être pas aussi explicite que de s’asseoir et de chercher la solution Big-O, mais cela crée une prise de conscience du problème - et cela vous oriente vers la recherche d’une réponse plus efficace et la résolution de problèmes d’approche vous pourriez prendre. par exemple. O (n * n) versus quelque chose de plus rapide, par ex. recherche de mots stockés dans une liste ou stockés dans un tri (exemple artificiel)

Je trouve que cela fait une différence avec les structures de données que je choisirai d'utiliser et avec la façon dont je travaillerai sur un grand nombre d'enregistrements.

Answer 14

Un bon exemple pourrait être quand votre patron vous demande de faire un programme et que vous pouvez démontrer en utilisant la théorie de la complexité de calcul que ce que votre patron vous demande de faire n’est pas possible.