Подразделы

Другие разделы

Дата и время

24/12/2025 23:44:25

Авторизация

Математические основы анализа алгоритмов

Асимптотические обозначения Основные классы эффективности Индукция и инвариант Нижние границы эффективности Тривиальная нижняя граница Информационно-теоретическая нижняя граница

Тривиальная нижняя граница

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

Например, любой алгоритм для генерации всех перестановок `n` различных элементов должен принадлежать
`Omega(n!)`,
поскольку размер выходных данных равен `n!`. Эта граница —
плотная, так как хорошие алгоритмы для генерации перестановок затрачивают постоянное время
для поиска каждой из них.

--

В качестве другого примера рассмотрим вычисление полинома степени `n`
в конкретной точке `x` для заданных коэффициентов `a_n, a_{n-1},..., а_0`.
Легко видеть, что все коэффициенты должны быть обработаны любым алгоритмом вычисления
полинома. Таким образом, любой алгоритм вычисления полинома
должен иметь эффективность `Omega(n)`. Эта нижняя граница —
плотная, поскольку имеется алгоритм (схема Горнера) с линейным временем работы.

--

Тривиальная граница для вычисления произведения
двух матриц размером `n xx n` оказывается равной `Omega(n^2)` так как любой такой
алгоритм должен обработать `2n^2` элементов входных матриц и сгенерировать `n^2`
элементов произведения. Однако неизвестно, является ли эта граница плотной.

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

---

##### Задания для практики

Найдите тривиальные классы нижних границ для следующих задач и по возможности укажите, плотная ли эта граница.\
а) Поиск наибольшего элемента массива.\
б) Проверка полноты графа, представленного матрицей смежности.\
в) Генерация всех подмножеств `n`-элементного множества.\
г) Определение того, все ли `n` действительных чисел различны.

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Математические основы анализа алгоритмов

Тривиальная нижняя граница