Нижние и верхние оценки.

  Д.Кнут. Искусство программирования для ЭВМ. тт 1-3. Москва. Мир. 1996-1998 Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999. Препарата Ф., Шеймос М. Вычислительная геометрия. Москва. Мир. 1989  

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

Алгоритмом m называется формально описанная процедура, имеющая некоторый набор входных данных In(m) и выходных данных Out(m). Вводится некоторый параметр, оценивающий объем входных данных N=N(In(m)). Будем называть этот параметр размером входных данных. Заметим, что, на самом деле, алгоритм решает некоторую формально поставленную задачу z, имеющую те же самые входные и выходные данные.

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

Для оценки времени работы алгоритма с каждой допустимой операцией ассоциируется время ее выполнения. Временем выполнения реализации алгоритма T(m) для определенных начальных данных называется сумма времен выполнения всех операций алгоритма при выполнении данной реализации.

Верхней оценкой времени выполнения алгоритма m называется такая функция F(N), что для любого набора входных данных In(m) размером не более N время выполнения алгоритма не будет превосходить F (N). Будем говорить, что задача z имеет верхнюю оценку времени решения F (N), если существует алгоритм m с верхней оценкой времени выполнения F (N).

Разумно задаться вопросом: а для любого ли алгоритма существует его верхняя оценка времени работы? Элементарно привести пример, для которого верхней оценки времени работы не существует (например, можно рассмотреть задачу выписывания всех десятичных знаков обычного целого числа). Однако, если количество различных вариантов входных данных объема N алгоритма для любого N конечно, то легко показать, что верхняя оценка времени работы алгоритма существует. Нас интересуют алгоритмы, которые можно реализовать на компьютере. Но у компьютера конечное количество ячеек памяти, поэтому и количество их комбинаций конечно. В таком случае на компьютере можно задать только конечное количество вариантов входных данных для любой задачи.

Последний факт очевиден, но, все же, требует доказательства. Доказательство строится от противного: допустим, количество различных вариантов наборов значений ячеек пямяти компьютера N, а задача имеет большее количество наборов исходных данных. В таком случае найдется хотя бы два варианта исходных данных задачи, соответствующих одному и тому же набору значений ячеек памяти компьютера, что противоречит тому, что мы можем задать на компьютере все варианты исходных данных задачи.

Итак, мы получили, что для всех алгоритмов, которые можно реализовать на компьютере существует верхняя оценка времени работы. На самом деле, этот факт не стоит ничего, т.к., с одной стороны, функция F (N) может очень быстро расти, а с другой, конечность количества ячеек компьютера всегда вступает в противоречие с бесконечностью мира. Например, конечность количества ячеек делает бессмысленным рассмотрение функции F (N) для любого натурального N.

Нижней оценкой времени выполнения алгоритма m называется такая функция j(N), что для любого N найдется такой набор входных данных алгоритма размером N, что время работы данного алгоритма на указанных данных будет не меньше j(N).

Нижней оценкой времени решения задачи z называется такая функция j(N), что для любого алгоритма, решающего данную задачу, j(N) будет нижней оценкой времени работы данного алгоритма.

Будем говорить, что задача z₁ сводится к задаче z₂ за время g(N), если

· входные данные задачи z₁, имеющие объем N, могут быть приведены к входным данным задачи z₂, при этом входные данные задачи z₂ тоже имеют объем N;

· выходные данные задачи z₂ могут быть приведены к выходным данным задачи z₁,

и все это за суммарное время g(N) (т.е. суммарное время выполнения алгоритмов приведения = g(N)). По аналогии, можно говорить, что алгоритм m₁ сводится к алгоритму m₂ за время g(N) (определение аналогично).

Теорема 1. Если задача z₁ сводится к задаче z₂ за время g(N) и задача z₂ имеет верхнюю оценку времени решения j₂(N), то задача z₁ имеет верхнюю оценку времени решения j₁(N) = j₂(N) + g(N).

Теорема 2. Если задача z₁ сводится к задаче z₂ за время g(N) и задача z₁ имеет нижнюю оценку времени решения j₁(N), то задача z₂ имеет нижнюю оценку времени решения j₂(N) = j₁(N) - g(N).

Доказательство теорем тривиально.

Введем обозначения.

g(n)=O(f(n)) если $ N₀>0 и С>0, такие что " n>N₀: g(n) £ C f(n)

g(n)=o(f(n)) если " С>0 $ N₀>0, такое что " n>N₀: g(n) £ C f(n)

g(n)=Q(f(n)) если $ N₀>0 и С₁, С₂>0, такие что " n>N₀:

С₁ f(n) £ g(n) £ С₂ f(n)

g(n)=W(f(n)) если $ N₀>0 и С>0, такие что " n>N₀: g(n) ³ C f(n)

Сортировки

Дата добавления: 2015-10-30