Математическая логика и теория алгоритмов

2.7 Характеристики сложности алгоритмов

назад | оглавление | вперёд

 

       Различные подходы к уточнению понятия «алгоритм» позволяли изучать принципиальную возможность решения некоторой математической задачи. (Здесь речь идет об общих задачах, в которых исходные данные могут варьироваться). Однако теоретическая возможность алгоритмического решения задачи еще не гарантирует практическую реализуемость алгоритма. Поэтому необходимо ввести характеристики алгоритмов, которые бы показывали степень практической реализуемости алгоритмов. Другая причина, по которой необходимы такие характеристики, – необходимость сравнения эффективности различных алгоритмов, которые решают одну и ту же задачу.

       При решении некоторой задачи P алгоритмом A обычно рассматривают такие характеристики:

       Для определения временной сложности алгоритма вместо общего числа шагов алгоритма можно также использовать количество операций определенного вида. Аналогично можно определить средние величины временной и емкостной сложности алгоритма. Сложность задачи P – это сложность наилучшего алгоритма, известного для ее решения, т.е. (минимум берется по всем алгоритмам для задачи P).

       Введем понятие верхнего и нижнего порядка функции относительно другой функции. Назовем арифметическую функцию f(x) функцией одного верхнего порядка с функцией g(x), т.е. f(x)=O(g(x)), если существует такая натуральная константа C и некоторое натуральное N0, что для всех x ≥ N0.

       Назовем арифметическую функцию f(x) функцией одного нижнего порядка с функцией g(x), т.е. f(x)=Ω(g(x)), если существует такая натуральная константа C и некоторое натуральное N0, что для всех x ≥ N0.

       Арифметическая функция f(x)функция одного порядка с функцией g(x), если она одного верхнего и одного нижнего порядка с функцией g(x), т.е. f(x)=O(g(x)) и f(x)=Ω(g(x)).

Пример 1.Пусть f(x)=log x и g(x)=x. Tогда существует положительная константа C, что log x ≤ C*x при x ≥ 1 , т.е. f(x)=O(g(x)).

       Функция одного верхнего порядка с полиномиальными функциями называется полиномиальной функцией. Это не только все полиномы, но и некоторые трансцендентные функции. Все остальные функции есть экспоненциальные в широком смысле этого слова. Но в строгом смысле слова экспоненциальными называются функции одного нижнего порядка с экспонентой. Тогда функции между экспоненциальными и полиномиальными называются субэкспоненциальными функциями. Экспоненциальные функции выделяются по скорости еще на несколько классов.

       Арифметические функции f(x) и g(x) называются полиномиально-связанными или полиномиально-эквивалентнтными, если существуют такие многочлены P1(x) и P2(x) и некоторое натуральное N0, что f(x) ≤ P1(g(x)) и g(x) ≤ P2(f(x)) для всех x ≥ N0.

Пример 2.Две функции f(x)=2x +3 и g(x)=x3 полиномиально связаны или эквивалентны, поскольку существуют два полинома P1(x)=x и P2(x)=x3 таких, что f(x) ≤ P1(g(x))=x3 и g(x) ≤ P2(f(x))=(2x+3)3.

       Рассмотрим задачу сортировки массива из n элементов. Хорошо известны алгоритмы решения этой задачи. В качестве временной сложности алгоритма сортировки используют две характеристики – количество сравнений элементов T1 и количество пересылок элементов T2, необходимых в ходе работы алгоритма. Для метода пузырьковой сортировки показано, что T1(n)=O(n2) и T2(n)=O(n2). Однако существуют алгоритмы, например алгоритм Хоара, который имеет лучшую верхнюю оценку временной сложности, чем метод пузырьковой сортировки. В частности, T1(n)=O(n log n) и T2(n)=O(n log n). Для задачи сортировки доказана нижняя оценка временной сложности T1(n) ≥ C1 * nlogn и T2(n) ≥ C2 * nlogn при или T1(n)=Ω(nlogn), T2(n)=Ω(nlogn), т.е. для сортировки массива требуется как минимум C * nlogn сравнений и пересылок. Таким образом, сложность задачи сортировки массива из n элементов имеет порядок nlogn при .

       Рассмотрим известный алгоритм сложения двух чисел столбиком. Входные данные – два числа, записанные в десятичной системе. Будем считать, что числа имеют n десятичных цифр в своем представлении. В качестве временной сложности этого алгоритма будем использовать количество операций сложений цифр, которое требуется для получения результата. Максимальное число сложений получается в случае, когда происходит перенос разряда для каждой цифры, т.е. T(n)=n + n + 1=2n + 1=O(n). Очевидно, что емкостная сложность M(n)=O(n).

       Определим сложность задачи сложения двух натуральных чисел при вычислении на машине Тьюринга. На вход МТ подаются две последовательности десятичных чисел. Внешний алфавит такой МТ содержит десятичные цифры и пустой символ, т.е. A={*,0,1,2,...,9}, где * – пустой символ.
       Начальная конфигурация выглядит так *q1an-1an-2...a1*bn-1bn-2...b1**. В общих чертах поведение МТ можно описать так. Сначала головка перемещается к концу второй последовательности стирает младший разряд, затем перемещается к младшему разряду первого числа и заменяет его на сумму младших разрядов и т.д.
       В качестве меры временной сложности данного алгоритма будем использовать количество выполненных команд МТ для перехода из начальной конфигурации в заключительную, т.е. на ленте записан результат сложения в виде последовательности десятичных цифр и головка установлена на первой цифре. Емкостная сложность вычислений на МТ определяется количеством ячеек ленты, которые заполнены непустыми символами либо посещались головкой во время работы МТ.
       Не трудно подсчитать общее количество действий и задействованных ячеек, T(n)=O(n2), M(n)=O(n). При этом для получения одного разряда результата требуется порядка n действий. Таким образом, временные сложности алгоритма сложения столбиком и алгоритма сложения на МТ полиномиально эквивалентны.

Пример 3.Арифметическая функция f(x,y)=x+y является примитивно рекурсивной, поскольку получена при помощи операции примитивной рекурсивной функции.
       Действительно,
       ,
       где h(x,y,z)=S(U33(x,y,z)). Поскольку функции g и h являются примитивно рекурсивными, то и функция f является примитивно рекурсивной. Процесс получения функции f можно представить графически в виде дерева
       
       В качестве временной сложности можно использовать количество операций суперпозиции, примитивной рекурсии и минимизации, которые необходимы при получении функции. Количество вершин в дереве заменит емкостную сложность получения рекурсивной функции. В данном случае T=2, M=5.


назад | оглавление | вперёд