САОД Методы анализа, страница 4

.

Правило произведений. Если T₁(n) и Т₂(п) имеют степени роста O(f₁(n)) и O(f₂(n)) соответственно, то произведение T₁(n)T₂(n) имеет степень роста O(f₁(n) f₂(n)).

Доказательство аналогично доказательству правило сумм.

Следствие правила произведений. O(cf(n)) эквивалентно О(f(п )), где с — положительная константа. Иными словами положительную константу можно вносить и выносить из-под асимптотической функции.

Например, О(2п²) эквивалентно О(п²).

1.3.6Ограниченность показателя функции роста

Пусть даны две программы, время выполнения одной O(n²), а вторая O(n³), причем при определенной комбинации компилятора ПК одна программа выполнятся за 100n², а вторая 5n³ может ли быть вторая программа предпочтительней другой? При n < 20, вторая функция предпочтительнее, т.к. для ее выполнения требуется меньше операций: 5n³ < 100n². Однако, при n > 20 первая программа становится предпочтительней. Вообще выбор определяется между программами на основе оценки трудоемкости и по возможности выбирается функция с полиномом меньшей степени. Чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере. Рассмотрим два случая использования этих алгоритмов: пусть в первом случае для решения задачи выделено машинное время T1 = 10000 мс, а во тором – в 100 раз больше (см таблицу).

Таблица

Функция трудоемкости решения задачи, f(n)	T1 = 10000 мс	T2 = 100*10000	затрат в 100 раз выше
	Размерность задачи, решаемой за время T1 и T2
	n1	n2
100n²	10	100	рост размерности задачи в 10 раз
5n³	12	60	в 5 раз

То есть, если выделено T₁ времени на ЭВМ для решения задачи этими алгоритмами, тогда мы успеем решить задачу размерности 10. Заплатив за время в 100 раз больше, и получив время в 100 раз больше, мы можем за новое время решить задачу размерности 100 и 60.

Вывод: увеличивая время выполнения на прежних ПК эффективность решаемой задачи (размерность) уменьшается и возможна ситуация, когда на увеличение размерности хотя бы на единицу потребуется времени неизмеримо много.

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

Практически вычислимыми, т.е. реализуемыми за приемлемое время являются алгоритмы полиномиального класса трудоемкости – это алгоритмы для которых асимптотическая оценка функции роста трудоемкости алгоритма представляет собой полином некоторой степени O(f(n)) = n^k, где k – константа.

Рассмотрим основные классы алгоритмов на основе вида их функции роста.

1.3.7Основные классы эффективности

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

Класс трудоемкости	Вид функции трудоемкости	Название подкласса	Примечание	Пример алгоритма данного подкласса
Полиномиальный класс (Р-класс)	const		Алгоритм не зависит от длины входных параметров, то есть число операторов постоянно и не измениться не при каком случае.
	log n	логарифмический	Обычно такая зависимость появляется в результате сокращения размера задачи на постоянное значение на каждом шаге итерации алгоритма. Обратите внимание, что в логарифмическом алгоритме исключается работа со всеми входными данными	Алгоритм бинарного поиска (метод деления отрезка пополам) среди n элементов.
	n	Линейная	К этому подклассу относятся алгоритмы, выполняющие сканирование списка, состоящего из n элементов.	Поиск элемента массива из n методом последовательного перебора
		«n- логарифм n »	К этому подклассу относятся большое количество алгоритмов декомпозиции, где для каждого из n элементов необходимо применить эффективный (например) поиск за логарифмическое время	Эффективные алгоритмы сортировки: пирамидальная, фиксированное двухпутевое слияния
	n2	Квадратичная	подобная зависимость характеризует эффективность алгоритмов, содержащих два вложенных цикла, каждый из которых выполняется не более n раз	Простые схемы сортировки, например, пузырьковая,
		Кубическая	Как правило, подобная зависимость характеризует эффективность алгоритмов, содержащих три вложенных цикла	Простой алгоритм перемножения матриц
Не детерминировано-полиномиальный (NP-класс)		Экспоненциальная	Данная зависимость типична для алгоритмов, выполняющих обработку всех подмножеств некоторого множества, состоящего из n элементов.	Задача о ханойских башнях.
	n!	Факториальная	Данная зависимость типична для алгоритмов, выполняющих обработку всех перестановок некоторого множе­ства, состоящего из n элементов	Полный перебор всех сочетаний элементов исходного множества при поиске решения задачи.
	Часто термин "экспоненциальный" используется в широком смысле (в том числе и для всего класса) и означает очень высокие порядки роста, имеющий принципиально другой характер поведения по сравнению с полиномом некоторой степени.

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

Таблица 1

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

log_a n = log_a b log_b n.

Поэтому далее будем опускать основание логарифма, то есть log n.

Если считать, что числа соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму со временем работы T(log n) потребуется 20 микросекунд, а алгоритму со временем работы T(n²) – более 12 дней.

Существует и другая крайность: показательная функция 2ⁿ и функция n! – вычисление факториала. Обе эти функции имеют настолько высокий порядок роста, что его значение становится астрономически большим уже при умеренных зна­чениях n. Например, чтобы выполнить 2¹⁰⁰ операций компьютеру, имеющему производительность в один триллион операций в секунду, понадобиться без малого 4 • 1010 лет! Однако это ничто по сравнению со временем, которое затратит тот же компьютер на выполнение 100! операций.