Доброго времени суток, уважаемые форумчане.

Объясните мне, пожалуйста, что обозначает сложность алгоритма сортировки?
В частности меня интересуют обозначения типа O(n), O(n2), O(n log n) и тому подобное.

Убедительно прошу не давать ссылки на различные источники и не советовать гуглить.

Расскажите русским понятным языком, что обозначают эти штуки.

Заранее благодарен.

Примерное количество выполняемых итераций. n - входящее в алгоритм количество элементов. O(n) - значит количество итераций равно количеству элементов, O(n^2) - количество итерация равно квадрату количества входных элементов, O(log n) - количество итераций равно логарифму по основанию 2 от количества входных элементов и так далее...

14SatanA88, 
Как по мне здесь объяснено понятным русским языком.
http://www.intuit.ru/department/supercomputing/baseraspp/2/

С одной поправкой - не равно, а пропорционально. Т.е. если количество выполняемых действий равно 3*n, то сложность алгоритма тоже O(n). И, кстати, относится это не только к алгоритмам сортировки, но и алгоритмам вообще.

Это сообщение отредактировал(а) Фантом - 18.6.2011, 00:42

Это все верно, но по-моему в определении говорится о времени выполнения, а не числе итераций или действий. Например, я могу скопировать один массив в другой с помощью одной ассемблерной инструкции, но сложность алгоритма равна O(n), а не O(1).

спасибо, более или менее разобрался.

14SatanA88

Пара примеров для лучшего понимания. Рассмотрим алгоритм поиска элемента в не отсортированном массиве. Чтобы найти конкретный элемент, в худшем случае надо пройтись по всем. В этом случае функция зависимости количества итераций от количества элементов будет линейной (O(n)), т.е. если нарисовать график этой функции, получиться прямая. Если же отсортировать этот массив, бинарный поиск позволит найти элемент с логарифмической сложностью (O(log n)), т.е. зависимость логарифмическая. Нахождение элемента по индексу в обыкновенном массиве имеет константную сложность (O(1)), т.е. от количества этих элементов вообще не зависит. 

из того, что я начитал, вроде как O(log n) эффективней чем O(n*n)? так?
если я не ошибаюсь, логарифм - это показатель степени?

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

Логарифм - число, в степень которого надо возвести базу, чтобы получить некое число N.
Пример алгоритма с логарифмической сложностью - бинарный поиск. Базой здесь является 2, т.е.
X = log2(N)
говоря простым русским языком, в какую степень надо возвести число 2, чтобы получить N? Допустим у нас 1000 элементов в массиве, log2(1000)=9, т.е. 2 надо возвести в степень 9, чтобы получить N, т.е. число найдется за 9 итераций.

Это сообщение отредактировал(а) azesmcar - 17.6.2011, 08:52

azesmcar, огромное спасибо. щас все понятно.

Эффективнее - пожалуй. Всегда быстрее - нет. Быстрее при достаточно больших n - да.

Мне кажется, вы пытаетесь все упростить. Еще раз - алгоритм, обрабатывающий n элементов и имеющий сложность O(log n) в худшем случае выполняется за время C1*log(n), где C1 - неизвестная нам константа. Другой алгоритм со сложностью O(n * n) опять же в худшем случае требует времени C2 * n * n. С1 и С2 - неизвестные константы! Если C1 > C2, а n - небольшое число, то второй алгоритм может быть быстрее первого.

Пример из моей практики. Алгоритмы умножения больших чисел. Умножение в столбик работает быстрее алгоритма Карацубы, если умножаемые числа имеют длину менее 2000 бит (примерно). Хотя у алгоритм Карацубы имеет меньшую сложность.

Нет конечно, вы говорите не о О  а об Омега Большое, 
и то что вы говорите об Омега Большое все равно не верно.

Добавлено @ 23:25
O(п) это семейство алгоритмов. чье худшее время выполнения не превышает линейную сложность с точностью до произведения на константу. ЭТо более менее точное определение. То что вам написали выше ближе к определению символа ОМЕГА да и оно не точное.

Надо вначала понять что все эти классы это семейства множеств алгоритмов с определенными свойствами.
А потом понять эти свойства. 


Большинство программистов не дружат с этими определениями и не знают их. Увы

Это сообщение отредактировал(а) esperanto - 17.6.2011, 23:27

А какая в них польза? Если они работают на n стремящимся к бесконечности, а в реалии я работаю с конечным числом элементов.

В зависимости от Вашего конечного числа элементов и надо выбирать алгоритм. Всё просто - строите графики сложностей и смотрите какая сортировка лучше при Вашем числе элементов.

В задаче сортировки 10 000 000 элементов я точно не буду использовать пузырьковую сортировку с её O(n*n), вместо этого возьму, например, сортировку слияниями с O(n* log(n)).

А в каком случае будешь?