Анализ наихудших и средних случаев - это общеизвестные меры сложности алгоритма. Недавно сглаженный анализ стал еще одной парадигмой, объясняющей, почему некоторые алгоритмы, экспоненциальные в наихудшем случае, так хорошо работают на практике, например, симплексный алгоритм.
Мой вопрос - есть ли другие парадигмы для измерения сложности алгоритма? Меня особенно интересуют те, которые пытаются объяснить, почему некоторые алгоритмы с плохой сложностью в худшем случае хорошо работают на практике.
времени. Это дает некоторое объяснение того, почему ваш алгоритм работает хорошо.
[1] Р. Нидермейер, Приглашение к алгоритмам с фиксированными параметрами. Оксфордская серия лекций по математике и ее приложениям, издательство Оксфордского университета, Оксфорд, 2006.
Амортизируемая сложность объясняется тем, что некоторые операции могут быть дорогостоящими в худшем случае, но если учесть много операций, средняя стоимость одной операции хорошая.
Классическим примером является структура данных, которая очищается, когда заполняется, копируя все свои элементы в некоторое хранилище. Операция копирования может быть дорогой, но это происходит не часто - вам нужно вставить достаточно элементов в структуру данных, чтобы спровоцировать ее.