![]() |
|
![]() ![]() ![]() |
|
14SatanA88 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 393 Регистрация: 13.5.2010 Репутация: 1 Всего: 5 |
Доброго времени суток, уважаемые форумчане.
Объясните мне, пожалуйста, что обозначает сложность алгоритма сортировки? В частности меня интересуют обозначения типа O(n), O(n2), O(n log n) и тому подобное. Убедительно прошу не давать ссылки на различные источники и не советовать гуглить. Расскажите русским понятным языком, что обозначают эти штуки. Заранее благодарен. |
|||
|
||||
Cheloveck |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1578 Регистрация: 26.7.2008 Где: Тула Репутация: нет Всего: 32 |
Примерное количество выполняемых итераций. n - входящее в алгоритм количество элементов. O(n) - значит количество итераций равно количеству элементов, O(n^2) - количество итерация равно квадрату количества входных элементов, O(log n) - количество итераций равно логарифму по основанию 2 от количества входных элементов и так далее...
-------------------- ![]() |
|||
|
||||
Pavia |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 418 Регистрация: 6.12.2008 Репутация: 11 Всего: 12 |
14SatanA88,
Как по мне здесь объяснено понятным русским языком. http://www.intuit.ru/department/supercomputing/baseraspp/2/ |
|||
|
||||
Фантом |
|
|||
![]() Вы это прекратите! ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 1516 Регистрация: 23.3.2008 Репутация: 2 Всего: 49 |
С одной поправкой - не равно, а пропорционально. Т.е. если количество выполняемых действий равно 3*n, то сложность алгоритма тоже O(n). И, кстати, относится это не только к алгоритмам сортировки, но и алгоритмам вообще. Это сообщение отредактировал(а) Фантом - 18.6.2011, 00:42 |
|||
|
||||
afiskon |
|
||||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 294 Регистрация: 31.3.2011 Где: Россия, Москва Репутация: нет Всего: 4 |
Это все верно, но по-моему в определении говорится о времени выполнения, а не числе итераций или действий. Например, я могу скопировать один массив в другой с помощью одной ассемблерной инструкции, но сложность алгоритма равна O(n), а не O(1). |
||||
|
|||||
14SatanA88 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 393 Регистрация: 13.5.2010 Репутация: 1 Всего: 5 |
спасибо, более или менее разобрался.
|
|||
|
||||
azesmcar |
|
|||
![]() uploading... ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 1 Всего: 211 |
14SatanA88
Пара примеров для лучшего понимания. Рассмотрим алгоритм поиска элемента в не отсортированном массиве. Чтобы найти конкретный элемент, в худшем случае надо пройтись по всем. В этом случае функция зависимости количества итераций от количества элементов будет линейной (O(n)), т.е. если нарисовать график этой функции, получиться прямая. Если же отсортировать этот массив, бинарный поиск позволит найти элемент с логарифмической сложностью (O(log n)), т.е. зависимость логарифмическая. Нахождение элемента по индексу в обыкновенном массиве имеет константную сложность (O(1)), т.е. от количества этих элементов вообще не зависит. |
|||
|
||||
14SatanA88 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 393 Регистрация: 13.5.2010 Репутация: 1 Всего: 5 |
из того, что я начитал, вроде как O(log n) эффективней чем O(n*n)? так?
если я не ошибаюсь, логарифм - это показатель степени? в общем с логарифмами я не до конца понял. объясните пожалуйста, что это как показатель сложности. |
|||
|
||||
azesmcar |
|
|||
![]() uploading... ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 1 Всего: 211 |
Логарифм - число, в степень которого надо возвести базу, чтобы получить некое число N. Пример алгоритма с логарифмической сложностью - бинарный поиск. Базой здесь является 2, т.е. X = log2(N) говоря простым русским языком, в какую степень надо возвести число 2, чтобы получить N? Допустим у нас 1000 элементов в массиве, log2(1000)=9, т.е. 2 надо возвести в степень 9, чтобы получить N, т.е. число найдется за 9 итераций. Это сообщение отредактировал(а) azesmcar - 17.6.2011, 08:52 |
|||
|
||||
14SatanA88 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 393 Регистрация: 13.5.2010 Репутация: 1 Всего: 5 |
azesmcar, огромное спасибо. щас все понятно.
|
|||
|
||||
afiskon |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 294 Регистрация: 31.3.2011 Где: Россия, Москва Репутация: нет Всего: 4 |
Эффективнее - пожалуй. Всегда быстрее - нет. Быстрее при достаточно больших n - да. Мне кажется, вы пытаетесь все упростить. Еще раз - алгоритм, обрабатывающий n элементов и имеющий сложность O(log n) в худшем случае выполняется за время C1*log(n), где C1 - неизвестная нам константа. Другой алгоритм со сложностью O(n * n) опять же в худшем случае требует времени C2 * n * n. С1 и С2 - неизвестные константы! Если C1 > C2, а n - небольшое число, то второй алгоритм может быть быстрее первого. Пример из моей практики. Алгоритмы умножения больших чисел. Умножение в столбик работает быстрее алгоритма Карацубы, если умножаемые числа имеют длину менее 2000 бит (примерно). Хотя у алгоритм Карацубы имеет меньшую сложность. |
|||
|
||||
esperanto |
|
|||
![]() Бывалый ![]() Профиль Группа: Участник Сообщений: 194 Регистрация: 31.5.2003 Репутация: 2 Всего: 4 |
Нет конечно, вы говорите не о О а об Омега Большое, и то что вы говорите об Омега Большое все равно не верно. Добавлено @ 23:25 O(п) это семейство алгоритмов. чье худшее время выполнения не превышает линейную сложность с точностью до произведения на константу. ЭТо более менее точное определение. То что вам написали выше ближе к определению символа ОМЕГА да и оно не точное. Надо вначала понять что все эти классы это семейства множеств алгоритмов с определенными свойствами. А потом понять эти свойства. Большинство программистов не дружат с этими определениями и не знают их. Увы Это сообщение отредактировал(а) esperanto - 17.6.2011, 23:27 --------------------
B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET |
|||
|
||||
Pavia |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 418 Регистрация: 6.12.2008 Репутация: 11 Всего: 12 |
||||
|
||||
1000000dollars |
|
|||
![]() Бывалый ![]() Профиль Группа: Участник Сообщений: 231 Регистрация: 6.10.2007 Репутация: 1 Всего: 8 |
В зависимости от Вашего конечного числа элементов и надо выбирать алгоритм. Всё просто - строите графики сложностей и смотрите какая сортировка лучше при Вашем числе элементов. В задаче сортировки 10 000 000 элементов я точно не буду использовать пузырьковую сортировку с её O(n*n), вместо этого возьму, например, сортировку слияниями с O(n* log(n)). |
|||
|
||||
azesmcar |
|
|||
![]() uploading... ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 1 Всего: 211 |
||||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |