Есть ли метод для автоматического анализа алгоритмов во время выполнения?

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

Я прогуглил «Автоматический анализ алгоритма», который дал мне это, но это слишком математично. Я просто хочу простой пример в psuedocode, который я могу понять. Может быть, слишком конкретным, но я думал, что это стоило того.

Инструмент COSTA делает именно это, хотя во многих случаях он, как вы можете себе представить, дает сбой из-за проблем с вычислимостью . Есть много статей об этом; Анализ стоимости Java-байт-кода Э. Альбертом, П. Аренасом, С. Дженаимом, Дж. Пуэблой, Д. Занардини является хорошей отправной точкой.

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

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

Я знаю один подход к (полу) автоматизированному анализу среднего случая, а именно MaLiJAn ¹. Это очень похоже на анализ, который Кнут использует в TAoCP. Основная идея заключается в

• смоделировать программу (поток) как цепь Маркова,
• $n$
• $n$
• используйте компьютерную алгебру, чтобы получить среднюю стоимость (с учетом этих функций).

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

Все этапы, кроме экстраполяции, являются строгими [2], и было продемонстрировано, что метод воспроизводит хорошо известные результаты с высокой точностью - конечно, с учетом подходящих случайных входных выборок. Хотя нет никаких доказательств или даже приблизительной гарантии результатов (пока шаг экстраполяции является чисто эвристическим), результаты, полученные с помощью этого инструмента, хорошо подходят для экспериментов с трудно анализируемыми алгоритмами и формулированием гипотез [3,4].

1. Полное раскрытие: я был членом этой исследовательской группы и принимал участие в разработке инструмента.
2. Анализ максимального правдоподобия алгоритмов и структур данных У. Лаубе и М. Небел (2010) [ препринт ]
3. Проектирование быстрой сводной сортировки Java 7 с использованием MaLiJAn от S. Wild и др. (2012) [ препринт ]
4. Анализ максимального правдоподобия метода Форда – Фулкерсона на специальных графиках У. Лаубе и М. Небеля (2015) [ препринт ]

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

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

$\lambda\acute\upsilon\omega$

Одна статья, которую я нашел в Интернете, - это статья 1990 года: автоматический анализ алгоритмов в среднем случае Филиппом Флажоле, Полом Циммерманом и Бруно Салви .

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

Теперь я боюсь, что работа Флажолета и его коллег была очень математической, и я не ожидал бы, что многое будет легко читать.