Existe-t-il des outils permettant de déterminer l'analyse de code pour la complexité de Big-O?

Question

Je n’ai encore rien vu et je soupçonne qu’il est difficile de définir "n". étant donné qu'en général, pour analyser une fonction complexe, il y aurait plus qu'une ou deux variables à définir.

Il existe des outils d’analyse pour la complexité cyclomatique, mais en existe-t-il pour la complexité temporelle (et / ou spatiale)? Si oui lesquels, sinon, pourquoi pas? Est-ce infaisable? Impossible? Quelqu'un n'a tout simplement pas réussi?

Idéalement, il devrait exister quelque chose comme une complexité globale pour l'application (définition de différents "n" possibles) ainsi que pour chaque méthode de l'application

Éditer: Il semble donc qu’une solution exacte est impossible à cause du Problème stoppant , Une sorte d'approximation heuristique est-elle possible? Je réalise que, pour des raisons pratiques, un bon profileur donnera des informations beaucoup plus utiles, mais cela semble être un problème intéressant.

Aussi, qu'en est-il de celui qui calcule pour un certain sous-ensemble de programmes?

Answer 1

Malheureusement, ce problème s’appelle le problème d’arrêt .

Answer 2

Non, cela n’est pas possible, à cause du problème d’arrêt.

Si vous souhaitez améliorer vos applications, envisagez plutôt de profiler. Cela vous permettrait d'identifier précisément ce qui prend le plus de temps. Ainsi, vous ne perdez pas de temps à optimiser un algorithme O (n ^ 3) qui ne fonctionne que sur de petits ensembles de données.

Answer 3

Quelques réflexions:

Les ordinateurs réels sont des machines à états finis à peu près déterministes, le problème d’arrêt n’est donc pas une limitation pratique. Une limite pratique est un algorithme qui prend plus de temps à exécuter que vous ne le souhaitez, excluant toute méthode d'analyse par force brute.

Pour avoir une idée approximative de la complexité d'un algorithme, vous pouvez toujours l'exécuter sur un ensemble d'entrées aléatoires et mesurer le temps pris. Puis tracez une courbe dans les données.

L'analyse de la complexité temporelle des algorithmes peut être assez compliquée, nécessitant quelques étapes créatives. (Voir par exemple l'analyse de quicksort). Le problème est étroitement lié à la démonstration du théorème logique et à la vérification du programme. Il serait peut-être faisable de construire un outil utile permettant une solution semi-automatique de la complexité, c’est-à-dire un outil qui recherche systématiquement les solutions données à l'aide d'indices humains, mais ce n'est certainement pas facile.

Answer 4

Je n'ai jamais vu d'outil pour ce faire, mais nous utilisons des outils de profilage pour mieux cerner les goulets d'étranglement. Ce n'est pas toujours évident et j'ai été surpris à quelques reprises par des choses qui, selon moi, ont pris beaucoup de temps, et très peu, et inversement. Dans le monde .NET, j'ai utilisé ANTS et le < un href = "http://www.jetbrains.com/profiler/" rel = "nofollow noreferrer"> outils JetBrains .