Существуют ли какие-либо инструменты, которые могут определить выполнение анализа кода для сложности Big-O?

Question

Я ничего не видел там, и я подозреваю, что трудно определить " n " поскольку для анализа сложной функции обычно требуется не только одна или две переменные.

Существуют инструменты анализа для цикломатической сложности, но есть ли они для временной (и / или пространственной) сложности? Если да, то какие, если нет, то почему бы и нет? Это невыполнимо? Невозможно? Кто-то просто не дошел до этого?

В идеале это должно быть что-то вроде общей сложности для приложения (определяющего различные возможные n), а также для каждого метода в приложении

Изменить. Таким образом, кажется, что точное решение невозможно из-за проблемы с остановкой , однако, Возможно ли какое-то эвристическое приближение? Я понимаю, что для практических целей хороший профилировщик даст гораздо больше полезной информации, но это кажется интересной проблемой.

Кроме того, как насчет того, которое рассчитывает на определенное подмножество программ?

Answer 1

К сожалению, существует эта проблема, которая называется Проблема остановки ...

Answer 2

Нет, это невозможно из-за проблемы остановки.

Если вы хотите сделать это для улучшения своих приложений, вместо этого вы можете рассмотреть вопрос о профилировании. Это позволит вам точно определить, что на самом деле занимает больше всего времени. Таким образом, вы не тратите время на оптимизацию алгоритма O (n ^ 3), который работает только для небольших наборов данных.

Answer 3

Несколько мыслей:

Реальные компьютеры - это примерно детерминированные конечные автоматы, поэтому проблема остановки на самом деле не является практическим ограничением. Практическим ограничением является алгоритм, выполнение которого занимает больше времени, чем вы ожидаете, исключая любые методы анализа методом перебора.

Чтобы получить общее представление о сложности алгоритма, вы всегда можете запустить его на множестве случайных входов и измерить затраченное время. Затем построите кривую по данным.

Анализ временной сложности алгоритмов может быть довольно сложным, требующим некоторых творческих шагов. (См., Например, анализ быстрой сортировки). Проблема тесно связана с логическим доказательством теорем и верификацией программы. Возможно, было бы целесообразно создать полезный инструмент, позволяющий полуавтоматически решать сложные задачи, т. Е. Инструмент, который систематически ищет решения с учетом подсказок от человека, но это, безусловно, непросто.

Answer 4

Никогда не видел инструмента для этого, но мы используем инструменты профилирования, чтобы лучше понять, где находятся узкие места. Это не всегда очевидно, и я несколько раз удивлялся вещам, которые, по моему мнению, занимали много времени, фактически занимая совсем немного, и наоборот. В мире .NET я использовал ANTS и < a href = "http://www.jetbrains.com/profiler/" rel = "nofollow noreferrer"> инструменты JetBrains .