Есть ли способ автоматически вывести сложность алгоритма (Python)?

Question

[Mark Adams]

Наверно вопрос глупый, но возможно ли с помощью библиотек Python выводить сложность самых простых функций в формате O().

Comments

[sim3x]

Покажи пример функций?

[Mark Adams]

так а причем тут пример? для любых не особо сложных алгоритмов.

[sim3x]

Илья Кметь: приведи пример "не особо сложных алгоритмов"

Answer 1

[RedHairOnMyHead]

Сложность алгоритма рассчитывается из того, сколько строк кода и каких, есть ли вложенные циклы, рекурсии и т.д. Автоматически можно, если умудритесь очень умно запарсить исходник, чтобы различал рекурсию и т.д. Но это уже не функции, а другая программа)
Так же все зависит от того, как алгоритм "нарисован" и насколько он запутан.
Прям анализатор какой-то получился :D

Answer 2

[Wataru]

Нет нельзя. Потому что нельзя даже определить, завершается ли программа, или виснет. Это называется проблема остановки (https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D... Логически доказано, что невозможно автоматически решить ее.

Подобным образом можно доказать, что не существует программы, определяющей сложность любой программы.
Допустим, что такая программа есть. Напишем другую программу, которая анализирует входной исходный код этой первой программой (пусть она получила оценку f(N)), а потом делает что-то неважное (например прибавляет 1 к переменной) f(N)*N раз. Теперь запустим эту программу на собственном исходном коде. Она получит оценку своей сложности и потом сделает что-то в N раз больше. Т.е. фактически сделано f(N)*N операций, но программа же оценила этот код как O(f(N)) на этих входных данных, что неверно.

Можно написать что-то тупое и наивное, вроде подсчета количества вложенных циклов, но работать будет только в очень частных случаях и часто ошибаться.