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

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.

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.

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».

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.

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.

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…