Асимптотический анализ алгоритмов.

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

Итак, довольно часто мы встречаемся с обозначениями типа O(g(n)), Ω (g(n)), Θ (g(n)). Для начала я покажу список основных классов:

· f(n) = O(1) константа

· f(n) = O(log(n)) логарифмический рост

· f(n) = O(n) линейный рост

· f(n) = O(n*log(n)) квазилинейный рост

· f(n) = O(n^m) полиномиальный рост

· f(n) = O(2^n) экспоненциальный рост

Что же за загадочный символ О? Я решил разобраться в этом вопросе, и, после нескольких удачных попыток поиска в интернете информации, все же нашел ответ:

«Запись вида f(n) = O(g(n)) означает, что функция f(n) возрастает медленнее, чем функция O(g(n)), при с = с1 и n=N, где с1 и N могут быть сколь угодно большими числами. т.е. При c = c1 и n > = N, c*g(n) > =f(n).

Таким образом O – означает верхнее ограничение сложности алгоритма.»

(С) habrahabr.ru.

Теперь необходимо рассмотреть практический пример:

Возьмем задачу сортировки массива из 1 000 000 элементов. Рассмотрим сразу самый худший случай реализации. Для этого понадобится простой, с точки зрения реализации, алгоритм – пузырьком. Этот алгоритм позволяет отсортировать массив любой размерности без дополнительных выделений памяти. Реализация данного алгоритма была проведена мною на языке С++, с применением 2-х циклов (реализация этого алгоритма не такая сложная, было принято решение подробно не останавливаться на описании кода):

· Внешний

· Вложенный

В примере внешний цикл будет выполняться ровно n = 1 000 000 раз. Именно столько же раз будет выполнятся и вложенный цикл, итого: n^2 раз. Не сложно рассчитать общее количество итераций: 1 000 000 * 1 000 000 = 1 000 000 000 000 итераций. Предположим, что на исполнение каждой из них у нас уйдет 2 единицы времени (с1 = 4), тогда общее количество времени, затраченного на сортировку массива у нас будет равно 4 * f(n^2).

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

Что остается делать? Ответ сам приходит в голову – использовать реально существующий алгоритм Пиромидальной сортировки, сложностью О(n*log(n)), который будет быстрей на 277777131 час (данные взяты из интернета.). На этой счастливой ноте, пожалуй, закончим. Я, конечно, не уверен в целесообразности описания значения асимптотического анализа алгоритмов в данном реферате, но посчитал, что эта информация пригодиться несведущему.