Начало
Учебные материалы
Математические основы анализа алгоритмов
Асимптотические обозначения Основные классы эффективности Индукция и инвариант Нижние границы эффективности Тривиальная нижняя граница Информационно-теоретическая нижняя граница
Нижние границы эффективности
установить класс асимптотической эффективности (скажем, для наихудшего случая)
и посмотреть, где он находится в иерархии классов эффективности.
Например, сортировка выбором, эффективность которой квадратична,
является достаточно быстрым алгоритмом, в то время как алгоритм решения
задачи о ханойских башнях работает очень медленно в силу своей экспоненциальности.
Однако такое сравнение алгоритмов сродни сравнению
яблок с картошкой, поскольку эти алгоритмы предназначены для решения
совершенно разных задач.
--
Более "честный" подход состоит в ответе
на вопрос о том, как соотносится эффективность конкретного алгоритма с
другими алгоритмами для решения той же задачи. В этом случае сортировка выбором
оказывается медленным алгоритмом, поскольку имеются алгоритмы сортировки
со временем работы `O(n log n)`.
Алгоритм решения задачи о ханойской башне,
с другой стороны, оказывается наиболее быстрым из возможных алгоритмов для
решения поставленной задачи.
--
Когда мы хотим выяснить, как соотносится эффективность данного алгоритма
с эффективностями других алгоритмов для решения той же задачи, желательно
знать, какую наивысшую эффективность может иметь любой алгоритм, решающий
рассматриваемую задачу. Знание такой нижней границы может
подсказать, на что мы можем надеяться при попытках получить более эффективный
алгоритм для решения нашей задачи.
Если такая граница *плотная*, т.е. уже
имеется алгоритм, принадлежащий тому же классу эффективности, что и нижняя
граница, мы можем в лучшем случае получить только улучшение эффективности
на постоянный множитель.
--
Если же между эффективностью наиболее быстрого
алгоритма и наилучшей нижней границей имеется "зазор", то дверь для
дальнейшего возможного усовершенствования алгоритма остается не запертой: либо
может существовать более быстрый алгоритм, соответствующий нижней границе,
либо можно доказать существование лучшей нижней границы.
--
Для поиска нижней границы может использоваться и идея приведения задачи к другой форме. Чтобы показать,
что задача `P` как минимум столь же сложна, как и задача `Q` с известной нижней
границей, мы должны привести `Q` к `P` (не `P` к `Q`).
Любой алгоритм, который решает задачу `P`, будет также решать и задачу `Q`. Тогда нижняя граница
для задачи `Q` будет нижней границей и для задачи `P`.
--
Поскольку сложность многих задач неизвестна, метод приведения часто
используется для сравнения относительной сложности задач. Например, формула\
`x*y= ((x+y)^2-(x-y)^2)/4`\
доказывает, что задача вычисления произведения двух `n`-разрядных чисел и
возведение `n`-разрядного числа в квадрат принадлежат одному и тому же классу
эффективности, несмотря на кажущуюся большую простоту второй задачи по
сравнению с первой.
--
Следует различать класс нижней границы и минимально необходимое количество
определенных операций. Как правило, определение второй величины —
задача существенно более сложная, чем первая.
Например, мы можем сделать
немедленный вывод о том, что любой алгоритм для поиска медианы `n` чисел должен
иметь эффективность `Omega(n)`, но не так просто доказать, что любой
алгоритм для решения этой задачи, основанный на сравнениях, должен выполнить
как минимум `3 (n-1)//2` сравнений в наихудшем случае.
