Другие виды анализа времени выполнения, кроме наихудшего, среднего и т. Д.?

Вот несколько способов проанализировать время работы алгоритма:

1) Анализ наихудшего случая: время выполнения в худшем случае.

2) Анализ среднего случая: ожидаемое время работы на случайном экземпляре.

3) Амортизированный анализ: среднее время работы в наихудшей последовательности экземпляров.

4) Сглаженный анализ: ожидаемое время работы в худшем случайном возмущенном экземпляре.

5) Анализ общего случая: время выполнения в худшем из всех случаев, кроме небольшого подмножества случаев.

Мой вопрос: это полный список?

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

Хотя он не входит в сферу компетенции традиционного алгоритмического анализа, он интересен сам по себе. Идея в статье Afshani-Barbay-Chan (FOCS '09), которая обсуждает геометрический алгоритм, рассматривает производительность алгоритма без учета порядка ввода (который имеет отношение к их конкретной проблеме).

Это можно рассматривать как обобщение следующим образом: для каждого алгоритма разбейте входные данные на классы эквивалентности и рассмотрите производительность алгоритма как некую коллективную статистику по средней производительности для каждого из этих классов эквивалентности.

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

Не ясно, приведет ли это к каким-либо новым парадигмам анализа алгоритмов. Курс Тима Рафгардена имеет несколько отличных мотивирующих примеров и охватывает различные методы анализа алгоритмов.

У меня есть еще два списка, которые несколько похожи.

1. $O(c^n n^{O(1)})$$1 < c < 2$$k$$O(2^k n^{O(1)})$$k$$n$

2. $O(n \log n + k)$$k$

$O(n \log n)$

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

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

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

Биективный анализ - это способ сравнения двух алгоритмов (Spyros Angelopoulos, Паскаль Швейцер: Пейджинг и обновление списка при биективном анализе. J. ACM 60, 2013): грубо говоря, алгоритм A лучше, чем алгоритм B, на входах длины n, если есть биекция f входов длины n такая, что A выполняет на входе x, по крайней мере, столько же, сколько B на f (x).

Конкурентный анализ

Используется для сравнения онлайн-алгоритмов с производительностью офлайн-алгоритмов. Смотрите страницу википедии . Проблема обновления списка - классический пример.

Конкурентный анализ. В алгоритме замены страниц один метод перевешивает другой, уменьшая количество пропущенных страниц. Меньшее количество пропущенных страниц иллюстрирует «меньшее время выполнения». Кроме того, конкурентный анализ - это метод сравнения двух методов. Хорошим справочником является «ОНЛАЙН ВЫЧИСЛЕНИЕ И КОНКУРЕНТНЫЙ АНАЛИЗ» от Аллана Бородина.