| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сложность алгоритмов сортировки |
| Автор: 14SatanA88 16.6.2011, 16:04 |
| Доброго времени суток, уважаемые форумчане. Объясните мне, пожалуйста, что обозначает сложность алгоритма сортировки? В частности меня интересуют обозначения типа O(n), O(n2), O(n log n) и тому подобное. Убедительно прошу не давать ссылки на различные источники и не советовать гуглить. Расскажите русским понятным языком, что обозначают эти штуки. Заранее благодарен. |
| Автор: Cheloveck 16.6.2011, 17:42 |
| Примерное количество выполняемых итераций. n - входящее в алгоритм количество элементов. O(n) - значит количество итераций равно количеству элементов, O(n^2) - количество итерация равно квадрату количества входных элементов, O(log n) - количество итераций равно логарифму по основанию 2 от количества входных элементов и так далее... |
| Автор: Pavia 16.6.2011, 18:20 |
| 14SatanA88, Как по мне здесь объяснено понятным русским языком. http://www.intuit.ru/department/supercomputing/baseraspp/2/ |
| Автор: Фантом 16.6.2011, 21:53 | ||
С одной поправкой - не равно, а пропорционально. Т.е. если количество выполняемых действий равно 3*n, то сложность алгоритма тоже O(n). И, кстати, относится это не только к алгоритмам сортировки, но и алгоритмам вообще. |
| Автор: afiskon 17.6.2011, 06:22 | ||||
Это все верно, но по-моему в определении говорится о времени выполнения, а не числе итераций или действий. Например, я могу скопировать один массив в другой с помощью одной ассемблерной инструкции, но сложность алгоритма равна O(n), а не O(1). |
| Автор: 14SatanA88 17.6.2011, 07:59 |
| спасибо, более или менее разобрался. |
| Автор: azesmcar 17.6.2011, 08:11 |
| 14SatanA88 Пара примеров для лучшего понимания. Рассмотрим алгоритм поиска элемента в не отсортированном массиве. Чтобы найти конкретный элемент, в худшем случае надо пройтись по всем. В этом случае функция зависимости количества итераций от количества элементов будет линейной (O(n)), т.е. если нарисовать график этой функции, получиться прямая. Если же отсортировать этот массив, бинарный поиск позволит найти элемент с логарифмической сложностью (O(log n)), т.е. зависимость логарифмическая. Нахождение элемента по индексу в обыкновенном массиве имеет константную сложность (O(1)), т.е. от количества этих элементов вообще не зависит. |
| Автор: 14SatanA88 17.6.2011, 08:17 |
| из того, что я начитал, вроде как O(log n) эффективней чем O(n*n)? так? если я не ошибаюсь, логарифм - это показатель степени? в общем с логарифмами я не до конца понял. объясните пожалуйста, что это как показатель сложности. |
| Автор: azesmcar 17.6.2011, 08:50 | ||
Логарифм - число, в степень которого надо возвести базу, чтобы получить некое число N. Пример алгоритма с логарифмической сложностью - бинарный поиск. Базой здесь является 2, т.е. X = log2(N) говоря простым русским языком, в какую степень надо возвести число 2, чтобы получить N? Допустим у нас 1000 элементов в массиве, log2(1000)=9, т.е. 2 надо возвести в степень 9, чтобы получить N, т.е. число найдется за 9 итераций. |
| Автор: 14SatanA88 17.6.2011, 08:53 |
| azesmcar, огромное спасибо. щас все понятно. |
| Автор: afiskon 17.6.2011, 10:33 | ||
Эффективнее - пожалуй. Всегда быстрее - нет. Быстрее при достаточно больших n - да. Мне кажется, вы пытаетесь все упростить. Еще раз - алгоритм, обрабатывающий n элементов и имеющий сложность O(log n) в худшем случае выполняется за время C1*log(n), где C1 - неизвестная нам константа. Другой алгоритм со сложностью O(n * n) опять же в худшем случае требует времени C2 * n * n. С1 и С2 - неизвестные константы! Если C1 > C2, а n - небольшое число, то второй алгоритм может быть быстрее первого. Пример из моей практики. Алгоритмы умножения больших чисел. Умножение в столбик работает быстрее алгоритма Карацубы, если умножаемые числа имеют длину менее 2000 бит (примерно). Хотя у алгоритм Карацубы имеет меньшую сложность. |
| Автор: esperanto 17.6.2011, 23:22 | ||||
Нет конечно, вы говорите не о О а об Омега Большое, и то что вы говорите об Омега Большое все равно не верно. Добавлено @ 23:25 O(п) это семейство алгоритмов. чье худшее время выполнения не превышает линейную сложность с точностью до произведения на константу. ЭТо более менее точное определение. То что вам написали выше ближе к определению символа ОМЕГА да и оно не точное. Надо вначала понять что все эти классы это семейства множеств алгоритмов с определенными свойствами. А потом понять эти свойства. Большинство программистов не дружат с этими определениями и не знают их. Увы |
| Автор: Pavia 18.6.2011, 07:06 | ||
А какая в них польза? Если они работают на n стремящимся к бесконечности, а в реалии я работаю с конечным числом элементов. |
| Автор: 1000000dollars 22.6.2011, 11:10 | ||
В зависимости от Вашего конечного числа элементов и надо выбирать алгоритм. Всё просто - строите графики сложностей и смотрите какая сортировка лучше при Вашем числе элементов. В задаче сортировки 10 000 000 элементов я точно не буду использовать пузырьковую сортировку с её O(n*n), вместо этого возьму, например, сортировку слияниями с O(n* log(n)). |
| Автор: azesmcar 22.6.2011, 12:01 | ||
А в каком случае будешь?  |
| Автор: Pavia 22.6.2011, 20:26 | ||
Посмотрю я на тебя как ты это будешь делать если у тебя будет квантовый компьютер. |
| Автор: 1000000dollars 23.6.2011, 09:27 | ||||
В пределах доступной оперативной памяти, потому что сортировка пузырьком не требует дополнительной памяти (под один элемент - можно не считать), в то время как сортировка слияниями - требует в общем случае в два раза больше памяти, чем сортируемых данных. Очевидно, что если я могу не использовать диск - я его и не буду использовать (обращение к диску очень медленное и оно сожрёт весь выигрыш), а если мне всё равно придётся его использовать - то почему бы не занять в два раза больше памяти? То есть с формальной точки зрения пузырёк не нужен, а с практической - я не буду городить сортировку слияниями, чтобы отсортировать 20 элементов Теория вычислительной сложности - только инструмент, который (как и любой другой) надо применять с умом
Вот когда будет - тогда и буду смотреть, что в нём и как, а пока что это пустые сотрясения воздуха |
