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

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

Например, любой алгоритм для генерации всех перестановок `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` действительных чисел различны.