Программа / алгоритм, чтобы найти временную сложность любой данной программы

Question

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

Ввод: любая программа (P) [на любом языке или на определенном языке]

Вывод: временная сложность этой программы (P).

Были ли какие-либо предыдущие попытки написать такую ​​программу? Есть ли алгоритмы для этой цели?

Если это так, пожалуйста, предоставьте необходимые ссылки, ссылки или любые возможные рекомендации.

Answer 1

Нет. Это невозможно. Это форма проблемы остановки .

Answer 2

Доказать сложность произвольного алгоритма невозможно, но в принципе вы можете оценить его:

1. выберите n, размер ввода
2. запустить алгоритм
3. соблюдать t (n), время, необходимое для запуска алгоритма для ввода размера n
4. выберите другой n, повторяйте шаги 2 и 3, пока у вас не будет много данных
5. регрессия t (n) на n, n ^ k, log (n), n log (n), n !, или любом другом термин, который может быть подходящим
6. выберите термин со статистической значимостью и объявите, что быть вашей оценочной сложности алгоритма

Существует множество ловушек в этом подходе.

1. Это ничего не докажет, только оценка
2. Если t (n) становится действительно большим для больших n, потребуется много времени, чтобы собрать достаточно данных для вашего анализа

3. Есть много способов, которыми этот подход можно обмануть, если вы не используете огромные значения из п. Например, этот алгоритм будет выглядеть как O (1), если вы не используете астрономические значения для n

   sleep for 10 days
   run an O(n log(n)) sorting algorithm
   

И другие пользователи SO могут придумать еще больше. Но в некоторых случаях, например, когда вы выполняете анализ сложности алгоритма и хотите проверить его эмпирически, это все еще полезный подход.

Answer 3

мы не можем ввести еще несколько переменных в сам алгоритм и найти сложность так же, как мы делаем это вручную. как например, у нас может быть переменная в сортировке вставки, скажем, n = 0, которая отслеживает всю циклическую часть алгоритма, а затем дает ответ в виде O (n ^ 2)

Answer 4

Ну, я думаю, что вы делаете это, предполагая все случаи. 1: Как сначала создать модуль, который может извлечь каждую инструкцию 2: Создайте базу данных инструкций для соответствия с инструкцией программы. 3: вычислите сложность, выбрав соответствующую временную сложность, установленную вами в базе данных, и все.