Программа/алгоритм для нахождения временной сложности любой данной программы
Взгляд' Практика Программирования ' (TPOP) Kernighan & Пика. Это включает пример парсинга файлов CSV и в C и в C++. Но стоило бы прочитать книгу, даже если Вы не используете код.
(Предыдущий URL: http://cm.bell-labs.com/cm/cs/tpop/ )
2 ответа
Нет. Это невозможно. Это одна из форм проблемы остановки .
Доказательство сложности произвольного алгоритма - это невозможно, но в принципе вы могли бы это оценить:
- выбрать n, размер входа
- запустить алгоритм
- наблюдать t (n), время, необходимое для запуска алгоритма для входа размера n
- выберите другой n, повторяйте шаги 2 и 3, пока не получите много данных
- regress t (n) на n, n ^ k, log (n), n log (n), n !, или любые другие термин, который может быть подходящим
- , выберите термин со статистической значимостью и заявите, что как ваша оценка сложности алгоритма.
У этого подхода есть любое количество подводных камней
- Это ничего не докажет, только оценка
- Если t (n) становится действительно большим для большого n, потребуется долгое время соберите достаточно данных для анализа
Есть много способов обмануть этот подход, если вы не используете огромные значения из п. Например, этот алгоритм будет выглядеть как O (1), если вы не используете астрономические значения для n
сна в течение 10 дней запустить алгоритм сортировки O (n log (n))
И другие пользователи SO могут придумать гораздо больше. Но в некоторых случаях, например, когда вы проводите анализ сложности алгоритма и хотите проверить его эмпирически, это все же полезный подход.