Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 83
про «habracut» (он же спойлер) что-нибудь слышали?
Да уже сделал
Сортировать за O(n) на практике все-таки можно — поразрядной сортировкой. Нельзя только в теории, при неограниченной длине ключей и при n -> ∞ или когда сортировка должна быть основана только на отношении линейного порядка.
Хорошее замечание.
Вы правы, можно но это уже будут не comparison алгоритмы.
Применять их на практике достаточно не удобно, так как они требуют памяти и знание того, какого типа данные мы собираемся сортировать.
В статье я рассматривал, только классические алгоритмы, основаные на сравнении элементов входного массива и забыл упомянуть об этом в тексте.
Вы правы, можно но это уже будут не comparison алгоритмы.
Применять их на практике достаточно не удобно, так как они требуют памяти и знание того, какого типа данные мы собираемся сортировать.
В статье я рассматривал, только классические алгоритмы, основаные на сравнении элементов входного массива и забыл упомянуть об этом в тексте.
Это смотря для для чего ее использовать. Если сортировать длинные массивы чисел ограниченной разрядности, то как по мне — так поразрядная сортировка и удобна, и быстра. Но как любой нетривиальный алгоритм имеет свои плюсы и минусы. Например, очень неоптимальна для маленьких массивов.
Сам рассказ конечно интересный. Приятно прочесть что нибудь фундаментальное на хабре! Искренне мое вам уважение.
НО:
Вы рассказали про асимтотику, но про константы совершенно не раскрыли тему. Читая статью мне стало казаться, что пузырек всегда плох… а что нибудь с O*log(n) всегда прямо манна небесная. Вы бы сделали акцент что такой анализ хорош на БЕСКОНЕЧНЫХ N, когда константа C уже не сильно важна для анализа. Реальные массивы то ограниченые. В зависимости от N и точной константы C алгоритмы с полиномиальной сложностью вполне могут быстрее логорифмеческих.
Приведу пример не на сортировке а на умножении матриц-
Классический алгоритм умножения строки на столбец дает порядок O(n^3) а к примеру алгоритм Вейерштрасса дает O(n^2.73)… казалось бы счастье… но не всегда. тк коээфициент перед классическим алгоритмом будет порядка десятки а Вейерштрассе порядка 100.
Вот по этом стоит упомянуть все таки про Бесконечные N и константу по лучше.
Да и Вы бы хоть какой нибудь алгоритм сортировки кроме пузырька рассмотрели. Та же быстрая сортировка или сортировка вставками была бы в этой статье очень к месту
НО:
Вы рассказали про асимтотику, но про константы совершенно не раскрыли тему. Читая статью мне стало казаться, что пузырек всегда плох… а что нибудь с O*log(n) всегда прямо манна небесная. Вы бы сделали акцент что такой анализ хорош на БЕСКОНЕЧНЫХ N, когда константа C уже не сильно важна для анализа. Реальные массивы то ограниченые. В зависимости от N и точной константы C алгоритмы с полиномиальной сложностью вполне могут быстрее логорифмеческих.
Приведу пример не на сортировке а на умножении матриц-
Классический алгоритм умножения строки на столбец дает порядок O(n^3) а к примеру алгоритм Вейерштрасса дает O(n^2.73)… казалось бы счастье… но не всегда. тк коээфициент перед классическим алгоритмом будет порядка десятки а Вейерштрассе порядка 100.
Вот по этом стоит упомянуть все таки про Бесконечные N и константу по лучше.
Да и Вы бы хоть какой нибудь алгоритм сортировки кроме пузырька рассмотрели. Та же быстрая сортировка или сортировка вставками была бы в этой статье очень к месту
Спасибо за критику. Другие алгоритмы обязательно будут рассмотрены в продолжении статьи про Ω(g(n)), Θ(g(n)).
Более того, есть ещё очень частотный случай — эффективность отдельных алгоритмов на определенных наборах данных. Я хотел давно ещё написать статью про это, но сейчас лень искать и собрать обрывки своих работ.
Если вкратце, можно строить комбинированные алгоритмические решения, в которых на основе определенного анализа кода (иногда довольно трудоемкого) будет приниматься выбор, каким алгоритмом пользоваться.
И ещё вариант, над которым работал — построение комбинированного алгоритма (на примере сортировки Фон-Неймана с отсечением нижнего уровня дерева рекурсии, и сортировкой оставшихся массивов 2^l степени (где l — уровень дерева рекурсии, на котором происходит отсечение) другим алгоритмом сортировки.
Результаты были довольно интересными кстати :) У меня получилось, что при останове сортировки Фон-Неймана и переключении на сортировку вставками при длине массива <= 13 дает довольно существенный прирост во времени работы алгоритма.
Остапа понесло, затыкаюсь.
Если вкратце, можно строить комбинированные алгоритмические решения, в которых на основе определенного анализа кода (иногда довольно трудоемкого) будет приниматься выбор, каким алгоритмом пользоваться.
И ещё вариант, над которым работал — построение комбинированного алгоритма (на примере сортировки Фон-Неймана с отсечением нижнего уровня дерева рекурсии, и сортировкой оставшихся массивов 2^l степени (где l — уровень дерева рекурсии, на котором происходит отсечение) другим алгоритмом сортировки.
Результаты были довольно интересными кстати :) У меня получилось, что при останове сортировки Фон-Неймана и переключении на сортировку вставками при длине массива <= 13 дает довольно существенный прирост во времени работы алгоритма.
Остапа понесло, затыкаюсь.
Комбинирование разных алгоритмов сортировки является вполне нормальной и часто применяемой техникой, которая действительно дает хорошие результаты. Если взять пример немного по-проще вашего, то вполне нормально до некоторого не очень большого N применять все ту же всеми любимую сортировку пузырьком, а в случаях когда N становится большим переходить на quicksort.
> к примеру алгоритм Вейерштрасса дает O(n^2.73)
Наверное, всё-таки Штрассена.
Наверное, всё-таки Штрассена.
> В статье я рассматривал, только классические алгоритмы, основаные на сравнении элементов входного массива и забыл упомянуть об этом в тексте.
Да, это обязательно стоит упомянуть.
Да, это обязательно стоит упомянуть.
Да, кстати можно и за O(log(n)). :) Только для этого потребуется n * log(n) процессоров или специальная микросхема.
Самый простой и в то же время красивый алгоритм за O(log2n) описан у Кнута (Batcher sort), читал так же статью о сортировке за O(log1+en), при любом e > 1, но статья такая сложная, что не смог понять, как это реализовать на практике. Автор поста написал полезную для Хабра заметку, но не в курсе всех возможностей.
да, сейчас же на процессорном уровне еще и «предсказания» реализованы. Так что вообще не понятно, какая наилучшая оценка :)
Почти в любом случае лучше тот алгоритм, у которого меньше класс сложности. Как упомянуто в статье, даже на самом быстром компьютере, если у вас сложность O(n*n!) или если вы совсем не везучий — O(2^n) в общем случае ваша программа будет работать дольше, чем не очень быстрый компьютер с алгоритмом O(n*log(n)).
нет, это понятно. Суть в другом: если взять не самый-самый оптимальный алгоритм, но просто очень оптимальный и положить на прооптимизированное железо — какой будет порядок?
В общем случае — тот же самый. Обычно, если алгоритм полиномиальный к примеру, его не получится просто путем оптимизации железа сделать квазилинейным. Посмотрите пример пузырька в статье, там показано, что даже увеличив кол-во процессоров, при данном алгоритме, сложность останется O(n^2). Если у вас какое-то специфическое железо, под него нужен специфический алгоритм, чтобы работать быстро.
я не буду долго спорить, но железо может решить. Если для каждого шага пузырька мы будем делать не n/2 операций, а 3-5-7 (в связи с предсказанием), то сложность алгоритма легко деградирует до C*n
Операций вы должны будете выполнить ровно столько же, иначе будут случаи, когда вы не сможете отсортировать массив с определенным набором данных. В случае предсказания переходов, у вас будет просто более эффективно использоваться конвеер. А поскольку следующий шаг алгоритма вы не сможете выполнить не выполнив предыдущий (не изменяя сам алгоритм сортировки), то все, что вы получите (в случае пузырька) это уменьшение C в выражении C*f(n^2)
Эту статью нужно было начинать с соглашений, что мы работаем на машине Фон-Неймана с последовательностью команд и фиксированным набором элементырных операций (в теории выполняющихся за приблизительно равное время).
Алгоритмы на машинах с другой архитектурой будут иметь другую трудоемкость:
1. На суперкомпьютерах Cray ипользуются векторные процессоры — в них умножение матриц — одна машинная команда.
2. Алгоритмы симметичного шифрования (основанные на математических сложных задачах), такие, как RSA, на квантовых процессорах (да, их сейчас нет в продаже, но логика для них уже разработана) будут взламываться минут за 5 в худшем случае.
+ асимптотическая теория трудоемкости алгоритмов не рассматривает следующие аспекты:
1. Операция выделения/освобождения памяти — она тоже занимает время, и если память тормозная и выделение памяти используется часто, то это вносит свой вклад в трудоемкость.
2. Эффективность алгоритма по использованию памяти
Фактически общая целевая функция С оптимальности алгоритма A выглядит как
С(A) = a * Ft(A) + b * Fm(A)
Ft(A) — Оптимальность по трудоемкости
Fm(A) — Оптимальность по памяти
a,b — весовые коэффициенты, которые вы регулируете для вашей задачи при сравнении алгоритмов. Например, если нам не важна память, то b = 0.
Алгоритмы на машинах с другой архитектурой будут иметь другую трудоемкость:
1. На суперкомпьютерах Cray ипользуются векторные процессоры — в них умножение матриц — одна машинная команда.
2. Алгоритмы симметичного шифрования (основанные на математических сложных задачах), такие, как RSA, на квантовых процессорах (да, их сейчас нет в продаже, но логика для них уже разработана) будут взламываться минут за 5 в худшем случае.
+ асимптотическая теория трудоемкости алгоритмов не рассматривает следующие аспекты:
1. Операция выделения/освобождения памяти — она тоже занимает время, и если память тормозная и выделение памяти используется часто, то это вносит свой вклад в трудоемкость.
2. Эффективность алгоритма по использованию памяти
Фактически общая целевая функция С оптимальности алгоритма A выглядит как
С(A) = a * Ft(A) + b * Fm(A)
Ft(A) — Оптимальность по трудоемкости
Fm(A) — Оптимальность по памяти
a,b — весовые коэффициенты, которые вы регулируете для вашей задачи при сравнении алгоритмов. Например, если нам не важна память, то b = 0.
Отличный комментарий.
Да, действительно, если углубляться, то появляется множество нюансов, таких как, например, SMID и ему подобные.
Так же, как вы правильно заметили, оптимальные по времени алгоритмы обычно отличаются прожорливостью по памяти, из-за чего их применение может стать нецелесообразным.
ПС. Небольшое замечание: Требуемая память для работы алгоритма обычно заранее известна и выделяется единоразово, одном куском, тем самым потребляя совсем мало процессорного времени
Да, действительно, если углубляться, то появляется множество нюансов, таких как, например, SMID и ему подобные.
Так же, как вы правильно заметили, оптимальные по времени алгоритмы обычно отличаются прожорливостью по памяти, из-за чего их применение может стать нецелесообразным.
ПС. Небольшое замечание: Требуемая память для работы алгоритма обычно заранее известна и выделяется единоразово, одном куском, тем самым потребляя совсем мало процессорного времени
Наверное многие программисты читая эти строки, думают про себя о том, что они всю жизнь прекрасно обходились без всего этого и конечно же в этих словах есть доля правды, но если встанет вопрос о доказательстве эффективности или наоборот неэффективности какого-либо кода, то без формального анализа уже не обойтись, а в серьезных проектах, такая потребность возникает регулярно.Я не могу представить себе человека, который называет себя программистом, и не знает, что такое O(N), вы уж извините )
Я думаю вы правы, но статья ведь не об O(N) как таковом, а о том, что такое верхняя граница сложности алгоритма, как можно ее найти в общем случае и как ее применять чтобы определить хорошо или плохо рабобтает некий код.
Кгм =) Вы что, думаете, когда я пишу «O(N)», я и имею в виду сугубо «O(N)», а если человек не знает, к примеру, что такое O(N logN), то его уже можно простить? =)
Естественно, имелась в виду теория оценки сложностей как таковая. Это основы программирования, теории алгоритмизации и вычислений. И писать код, не умея оценивать, как долго он будет выполняться в худшем, среднем и лучшем случае — можно сказать, преступление.
Естественно, имелась в виду теория оценки сложностей как таковая. Это основы программирования, теории алгоритмизации и вычислений. И писать код, не умея оценивать, как долго он будет выполняться в худшем, среднем и лучшем случае — можно сказать, преступление.
Я с вами согласен, что это нужно знать, но вот про то, что все, кто программирует знают это — думаю слишком сильное заявление :)
А я не говорил, что все, кто программируют, знают это.
Я говорил, что если человек называет себя программистом, то обязан знать это.
А мы в реальности имеем полчища вебдевов, которые массив из 107 интов в оперативной памяти пузырьком сортируют (образно говоря).
Я говорил, что если человек называет себя программистом, то обязан знать это.
А мы в реальности имеем полчища вебдевов, которые массив из 107 интов в оперативной памяти пузырьком сортируют (образно говоря).
Хорошо если пузырьком. И ещё мало кто из таких погромистов думает о том, что оптимизировать можно затраты памяти, а можно количество итераций сокращать. И что два этих действия зачастую не могут быть выполнены одновременно. Обычно погоня за меньшим числом итераций ведёт к увеличению расхода памяти и наоборот.
Обычно в олимпиадных задачах дают ограничение и на время и на объем. Вот там уже приходится по настоящему думать, а не решать в лоб.
Обычно в олимпиадных задачах дают ограничение и на время и на объем. Вот там уже приходится по настоящему думать, а не решать в лоб.
Видно старания и подход к работе. Но название не совсем соответствует содержанию: речь была о методе, а рассказано было о применении его к конкретной задаче.
Вопрос немного не по теме статьи, но… как включить сглаживание в графиках gnuplot?
f(n) = O(n*log(n)) так и называется nlog(n), другого названия пока не придумали )
Квазилинейный рост, en.wikipedia.org/wiki/Big_O_notation
BTW, я в алгоритмах очень плохо разбираюсь :), подскажите, как вот такая сортировка называется:
for i in xrange( 0, N ) :
max = i
for j in xrange( i, N ) :
if arr[ j ] > arr[ i ] :
max = j
arr[ j ], arr[ i ] = arr[ i ], arr[ j ]
Перенесите в блог «Алгоритмы», там статья будет явно не лишней.
В целом статья неплохая и ее полезно почитать для понимания.
Но при этом есть и замечания. Например ваше формальное определение (1.1). Во-первых оно реально взорвало мне мозг, и это при том, что я уже знал формальное определение. Во-вторых, насколько я понимаю, вместо «g(n) >=f(n)» должно быть «с*g(n) >=f(n)». Но это уже и не так важно, поскольку сомневаюся, что многие, кто не знал определение до прочтения статьи, осилят ваш вариант. Думаю, что лучше поменять это определение на другое, например из этой статьи: algolist.manual.ru/misc/o_n.php, или из книги Кормена.
В целом статья неплохая и ее полезно почитать для понимания.
Но при этом есть и замечания. Например ваше формальное определение (1.1). Во-первых оно реально взорвало мне мозг, и это при том, что я уже знал формальное определение. Во-вторых, насколько я понимаю, вместо «g(n) >=f(n)» должно быть «с*g(n) >=f(n)». Но это уже и не так важно, поскольку сомневаюся, что многие, кто не знал определение до прочтения статьи, осилят ваш вариант. Думаю, что лучше поменять это определение на другое, например из этой статьи: algolist.manual.ru/misc/o_n.php, или из книги Кормена.
Спасибо, за то, что нашли ошибку, должно быть действительно «c*g(n) >= f(n)».
На счет определения, мне оно кажется достаточно понятным, по-крайней мере не менее понятным, чем в приведенной вами ссылке.
На счет перенести в алгоритмы, боюсь у меня не достаточно для этого кармы, т.к. это моя первая статья на Хабре.
На счет определения, мне оно кажется достаточно понятным, по-крайней мере не менее понятным, чем в приведенной вами ссылке.
На счет перенести в алгоритмы, боюсь у меня не достаточно для этого кармы, т.к. это моя первая статья на Хабре.
ХудШий, а не худЖей.
Огромное спасибо за статью, всегда пытался понять эти обозначения
Кстати, у некоторых особо просвящённых индусов может быть даже не экспоненциальный рост от объема данных, а факториальный. Была где-то хорошая статья в блоге про тех выдающихся людей, которые смогли такой алгоритм представить.
А вот и она
articles.org.ru/cn/showdetail.php?cid=6152
А вот и она
articles.org.ru/cn/showdetail.php?cid=6152
Ждем продолжения и развития темы :) Спасибо!
Предпоследний случай «почти» возможен. Если использовать параллельные вычисления / слияния массивов. Там почти C*n получается.
Полезная статья. Продолжайте, очень хорошо излагаете.
>Но оказывается, что сделать сортировку со сложностью O(n) в общем случае просто не возможно
Немного не согласен. Это не возможно лишь при сортировке сравнением, но весьма возможно при поразрядной или сортировке подсчетом.
А еще есть наивный алгоритм за O(n*n!) :-)
Немного не согласен. Это не возможно лишь при сортировке сравнением, но весьма возможно при поразрядной или сортировке подсчетом.
А еще есть наивный алгоритм за O(n*n!) :-)
>>Наверное многие программисты читая эти строки, думают про себя о том, что они всю жизнь прекрасно обходились без всего этого
Не скажите. Программисты, которые занимаются олимпиадным (=спортивным) программированием, всю жизнь именно этим и пользуются.
Не скажите. Программисты, которые занимаются олимпиадным (=спортивным) программированием, всю жизнь именно этим и пользуются.
Жду продолжения!
А что вы можете посоветовать почитать об эффективности алгоритмов?
А что вы можете посоветовать почитать об эффективности алгоритмов?
> Разобьем наш массив на 4 части и каждую часть поручим выполнять
> отдельному ядру. Что мы получим? На сортировку каждой части понадобится
> ровно O((n / 4)^2). Так как все части сортируются одновременно, то этот
> результат и будет конечным временем сортировки четырех подмассивов,
> размерностью n/4. Возведем получившееся
Вот действительно, что мы получим? С каких пор сортировку данных можно так просто «разрезать» на части? В очень редких случаях рез-т можно будет просто «склеить», а не сортировать повторно.
P. S. Слово «худжий» это что-то!… Автор, осиль уже спеллчекер, а?
> отдельному ядру. Что мы получим? На сортировку каждой части понадобится
> ровно O((n / 4)^2). Так как все части сортируются одновременно, то этот
> результат и будет конечным временем сортировки четырех подмассивов,
> размерностью n/4. Возведем получившееся
Вот действительно, что мы получим? С каких пор сортировку данных можно так просто «разрезать» на части? В очень редких случаях рез-т можно будет просто «склеить», а не сортировать повторно.
P. S. Слово «худжий» это что-то!… Автор, осиль уже спеллчекер, а?
Учимся читать текст целиком и осознавать прочитанное. Это сложнее, чем подмечать опечатки.
получив таким образом сложность равную O(1/16*n^2 + n), где n — итерации необходимые на сортировку итогового массива полученного конкатенацией четырех готовых подмассивов.
> Это сложнее, чем подмечать опечатки.
Именно, спеллчекер бы справился.
> итерации необходимые на сортировку итогового массива полученного конкатенацией четырех готовых подмассивов.
Я видел этот текст, вот только поскольку он приведён as is, без каких либо объяснений, то… вобщем опечатки не на руку автору.
Именно, спеллчекер бы справился.
> итерации необходимые на сортировку итогового массива полученного конкатенацией четырех готовых подмассивов.
Я видел этот текст, вот только поскольку он приведён as is, без каких либо объяснений, то… вобщем опечатки не на руку автору.
А теперь, вместо того, чтобы умничать (и минусовать) не по делу, пройди вот сюда, и почитай ответ автора: habrahabr.ru/blogs/algorithm/78728/#comment_2304009
Я сожалею, что банальная опечатка вызвала у вас столько негативных эмоций. Сейчас поправлю.
По повоту «резрезать», не могли бы вы конкретно указать на ошибку в логике или выводах? Повторно сортировать ничего не предлагается.
По повоту «резрезать», не могли бы вы конкретно указать на ошибку в логике или выводах? Повторно сортировать ничего не предлагается.
> банальная опечатка
Банальная опечатка это когда слово «худший» неправильно написано один раз. Когда вместо него повально употреблено «худжий», это уже банальная безграмотность…
Банальная опечатка это когда слово «худший» неправильно написано один раз. Когда вместо него повально употреблено «худжий», это уже банальная безграмотность…
> указать на ошибку в логике или выводах?
А где там выводы? Ни с того, ни с сего предлагается «возвести в квадрат и получить итоговую сложность равную O(1/16*n^2 + n)» — почему не в куб, или в ½?…
А где там выводы? Ни с того, ни с сего предлагается «возвести в квадрат и получить итоговую сложность равную O(1/16*n^2 + n)» — почему не в куб, или в ½?…
Потому-что алгоритм имеет сложность O(n^2)
> Потому-что алгоритм имеет сложность O(n^2)
А какой именно алгоритм? Сортировки с использованием 4-х отсортированных наборов данных, или?…
А какой именно алгоритм? Сортировки с использованием 4-х отсортированных наборов данных, или?…
Сортировки пузырьком, поскольку именно он и рассматривается в статье.
Разбиение на 4 части приведено просто как пример того, что обычно изменение (улучшение) аппаратной части без написания специального алгоритма под нее не дает большого выигрыша в скорости.
Разбиение на 4 части приведено просто как пример того, что обычно изменение (улучшение) аппаратной части без написания специального алгоритма под нее не дает большого выигрыша в скорости.
*Вспомнил, что завтра расчетку по матану сдавать :/ *
Небольшой хинт для программистов: что бы не терять время на сортировку пузырьковым методом при больших объёмах массива (например 1 000 000 000 эл-ов) — необходимо сначала отсортировать отрицательное число эл-ов, соответствующее по модулю требуемым и тем самым выиграть некоторое время!
Этот же принцип можно использовать при отрисовке сложных 3D сцен, отрисовывая сначала отрицательное количество полигонов. :)
Этот же принцип можно использовать при отрисовке сложных 3D сцен, отрисовывая сначала отрицательное количество полигонов. :)
Раз уж речь шла преимущественно о сортировке, думаю, не лишней будет эта ссылочка: www.sorting-algorithms.com/ =)
Хорошая статья. Спасибо автору. Считай, что доступным, не совсем академическим языком объяснил пару глав из «Искусства программирования» Кнута.
У меня не прогружаются картинки.
Хабр, верни картинки.
Рисунки сломались, похоже, не показывает
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Асимптотический анализ алгоритмов