Trouver par programmation la notation Landau (notation Big O ou Thêta) d'un algorithme?

11

J'ai l'habitude de chercher à la main la notation Landau (Big O, Theta ...) de mes algorithmes pour m'assurer qu'ils sont aussi optimisés que possible, mais quand les fonctions deviennent vraiment grandes et complexes, ça prend le pas trop de temps pour le faire à la main. il est également sujet aux erreurs humaines.

J'ai passé un peu de temps sur la codilité (exercices de codage / algo), et j'ai remarqué qu'ils vous donneront la notation Landau pour votre solution soumise (à la fois dans l'utilisation du temps et de la mémoire).

Je me demandais comment ils faisaient ça ... Comment feriez-vous?

Existe-t-il une autre solution que l'analyse lexicale ou l'analyse du code?

Cette question concerne principalement PHP et ou JavaScript, mais je suis ouvert à tout langage et théorie.

Julien L
la source
4
Vérifiez cette réponse de SO. Cela ressemble à ce que vous recherchez.
Déco
2
Si vous pouvez créer un programme qui résout ce problème pour chaque algorithme, vous deviendrez célèbre comme "l'homme qui a réfuté Turing".
user281377
1
Pour les preuves qu'il est généralement impossible de décider des durées de fonctionnement, voir ici et ici - les réponses là-bas s'avèrent encore plus que ce que vous demandez, en fait.
Alex ten Brink

Réponses:

13

Je me demandais comment ils faisaient ça ... Comment feriez-vous?

J'imagine qu'ils estiment en fait les mesures de Big O ... en exécutant le programme pour différentes tailles de problèmes, en mesurant l'utilisation du temps et de l'espace et en ajustant les courbes aux résultats.

Le problème avec cette approche est qu'elle peut se tromper si les fonctions de coût changent de forme lorsque N devient grand; par exemple 1000 N + N^1.5.

Existe-t-il une autre solution que l'analyse lexicale ou l'analyse du code?

L'analyse et l'analyse syntaxique ne sont pas suffisantes. Vous devez également raisonner sur le comportement de l'algorithme. Et faire cela automatiquement pour un algorithme inconnu auparavant est difficile.

Stephen C
la source
6
"il est difficile de le faire automatiquement pour un algorithme jusque-là inconnu" - Plus précisément: cela revient à résoudre le problème de l'arrêt.
Jörg W Mittag
Euh ... pas exactement. Résoudre le problème de l'arrêt serait équivalent à pouvoir le faire pour tous les algorithmes inconnus auparavant.
Stephen C
2
Oui désolé. Le faire pour un algorithme équivaut (ou plutôt implique) à prouver la terminaison.
Jörg W Mittag
1
Les aspects pratiques de ceci sont que 1) il est impossible de prouver ou d'infirmer la terminaison pour certains algorithmes, mais 2) la plupart des algorithmes n'ont pas cet obstacle théorique, mais 3) l'état de l'art en matière de preuve de théorème n'est pas suffisamment avancé pour être en mesure de le faire de toute façon ... sauf dans des cas relativement simples. D'où ma déclaration selon laquelle j'imagine qu'ils font cela d'une manière différente. Mais évidemment, nous ne pouvons pas être sûrs de la façon dont ils font vraiment cela sans regarder leur code.
Stephen C
3

Ils ne peuvent pas sans analyser le code.

Les exemples ci-dessous avec une «inflation / déflation» artificielle de la complexité prouvent que la simple mesure de la durée d'exécution du programme n'est pas suffisante pour estimer de manière fiable Big-O

void lets_trick_runtime(int n) {
   if (n == 10 || n == 25 || n == 118) {
      // unfair speed-up
      do_precalculated_solution_in_constant_time(n);
      return;
   }
   if (n == 11 || n == 26 || n == 119) {
      // unfair slow-down
      do_some_fake_processing_in_n_cube_time(n);
      return;
   }
   // fair solution
   do_general_solution_in_quadratic_time(n);
}

L'estimation du temps d'exécution ci-dessus serait susceptible de donner de fausses estimations - temps constant pour les valeurs noù il y a une solution pré-calculée et temps cubique pour les valeurs où les unfair slow-downcoups de pied - au lieu du temps quadratique «juste».

moucheron
la source
Cependant, s'ils arrivent à vérifier les cas «déloyaux», ils peuvent toujours supposer que le pire des cas estime en effet la complexité du Big-O.
Yam Marcovic
1

Je pense que ce n'est pas possible.

Si vous exécutez des tests avec un nombre fixe de tailles d'entrée différentes, vous pouvez facilement calculer un polynôme, qui se rapprochera très bien des durées d'exécution que vous avez mesurées. Vous vous retrouvez donc avec un polynôme pour chaque programme possible, ce qui signifie P = NP(ouais!;)).

Si vous essayez de le faire avec une manipulation symbolique, vous vous retrouvez au halting problem. Étant donné que vous ne pouvez pas décider si votre programme s'arrêtera jamais, vous ne pouvez pas décider de sa complexité d'exécution.

Il peut cependant exister des cas très particuliers où la dernière méthode est possible. Mais ces cas sont peut-être si petits, qu'il est douteux que les efforts soient payés.

SpaceTrucker
la source
1
+1, bien que je pense que le problème d'arrêt pourrait être considéré comme une rareté.
Yam Marcovic
0

Comment le ferais-je? La façon dont je résous presque tous les problèmes, je ne veux pas m'asseoir et résoudre . Je simule.

Pour de nombreux problèmes, il peut être suffisant d'exécuter votre algorithme plusieurs fois en utilisant une variété de tailles, puis d'ajuster une courbe de régression à ces résultats. Cela identifierait rapidement certains frais généraux «fixes» particuliers de votre algorithme (l'ordonnée à l'origine de la courbe) et comment il évolue à mesure que la taille de votre problème augmente.

Un bricolage sera nécessaire pour capturer des solutions particulièrement compliquées, mais surtout si vous cherchez juste une estimation approximative, vous devriez pouvoir l'obtenir de cette façon, et voir comment votre estimation diffère de vos résultats réels et décider si c'est une approximation acceptable.

La plus grande faiblesse dans mon esprit avec cette méthode est que si votre algorithme évolue vraiment mal, cette étape initiale "exécutez-le tout un tas de fois" va devenir laide. Mais franchement, c'est le cas, cela seul devrait être un indicateur que vous voudrez peut-être prendre du recul et reconsidérer les choses.

Fomite
la source
0

Mon intuition est qu'une solution générale à ce problème est impossible; affirmer, comme il le fait, des faits a priori sur le temps d'exécution des algorithmes sans les exécuter (vous faites allusion à l'analyse lexicale). Cela dit, il est possible pour un algorithme heuristique pour une classe d'algorithmes (probablement grande) (puisque nous le faisons tout le temps), mais un algorithme général pour ce faire serait équivalent à résoudre le problème Entscheidungsproblem qui est bien connu pour ne pas être possible (cf. Church, Turing, et al.). J'en suis à 99,9% sûr maintenant que j'y pense…

très stupide
la source