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

Question

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

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

В идеале было бы что-то вроде общей сложности для приложения (определение различных возможных «п» s), а также для каждого метода в приложении

Edit: Так что, похоже, как точное решение невозможно, так как из Halting Problem, однако, возможно ли какое-то эвристическое приближение? Я понимаю, что для практических целей хороший профилировщик предоставит гораздо более полезную информацию, но это кажется интересной проблемой.

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

Answer 1

К сожалению, эта проблема называется Halting problem ...

Answer 2

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

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

Answer 3

Никогда не видел инструмент для этого, но мы используем инструменты профилирования, чтобы лучше понять, где узкие места. Это не всегда очевидно, и я несколько раз удивлялся тем вещам, которые, как я думал, долгое время занимали очень мало и наоборот. В мире .NET я использовал ANTS и инструменты JetBrains.

Answer 4

Несколько thoughs:

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

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

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