Существует как минимум три (и более) независимых и ортогональных оси, вдоль которых может происходить асимптотический анализ алгоритмов: случай (лучший, средний, худший);связанный (большой-O, маленький-омега, тета);и следует ли учитывать амортизацию.
Случай описывает рассматриваемый класс затрат. Это буквально подмножество входов в алгоритм. При выполнении анализа асимптотической сложности естественно разделить входное состояние на подмножества на основе производительности алгоритма по отношению к элементам подмножества. Таким образом, у вас может быть лучший случай, для которого алгоритм работает асимптотически, насколько это возможно;подмножество, где оно работает асимптотически настолько плохо, насколько это возможно;или, в случае средней сложности, набор входных данных вместе с их относительным весом или вероятностью возникновения. В отсутствие специально описанного случая естественно предположить, что все входные данные включены и имеют одинаковый вес.
Граница описывает, как сложность алгоритма ведет себя асимптотически для входов определенного класса. Сложность может быть ограничена сверху, снизу или обоими;границы могут быть жесткими или нет;и хотя выбранная вами граница на практике может определяться рассматриваемым случаем (нижняя граница для наилучшего случая, верхняя граница для худшего случая и т. д.), теоретически выбор полностью независим.
Выполнен амортизированный анализна вершине основного анализа сложности и рассматривает не отдельные входы, а последовательности входов. Амортизированный анализ пытается объяснить, как ведет себя совокупная временная сложность последовательности операций. Например, рассмотрим простой случай вставки нового элемента в векторную структуру на основе массива. Если у нас достаточно мощности, операция O (1). если нам не хватает емкости, операция O (n). Если мы увеличиваем емкость вектора арифметически (добавляя, например, k новых точек каждый раз), то у нас будет O (1) доступов (k-1) / k времени, и O (n) доступов 1 / kвремени, для O (n) амортизируемой сложности. Однако, если мы геометрически увеличиваем емкость каждый раз, когда нам требуется больше емкости, то мы обнаруживаем, что последовательность добавлений будет иметь О (1) амортизированную сложность.
Действительно постоянные функции могут выполнять амортизированный анализ, но на самом деле нетпричина для этого. Амортизированный анализ имеет смысл только тогда, когда потенциально небольшое количество повторных запросов имеет низкую индивидуальную производительность, а большинство (асимптотически) запросов имеет асимптотически лучшую производительность.