Comments 27
Я бы посмотрел на реализацию пирамидальной сортировки на разных языках. Особенно транслируемых.
Сортировка вставками имеет сложность n2 на практике же приблизительное количество перестановок вычисляется по формуле n2/2.Вы забываете про O. В данном случае временная сложность O(n2), то есть время работы T(n) ограничено функцией C*n2 для некоторого C > 0.
Для доказательства был написан следующий код:Этот код ничего не доказывает, у вас просто частный случай. Доказывается эта формула в общем виде совсем не так.
Вообще говоря, при учете сложности алгоритмов на эту константу нечасто обращают внимание. Потому что важна именно зависимость скорости работы от размера входных данных. Для алгоритмов сортировок, основанных на сравнении элементов, доказано, что не может существовать алгоритма со сложностью лучшей, чем n*log(n).
Опять же, взять в сравнение эту самую сортировку вставками и, например, HeapSort. У второго алгоритма эта константа намного больше — сами операции более сложные, плохо используется кеш, и т.д. Но тем не менее, HeapSort лучше именно тем, что при достаточно больших значениях n он превзойдет InsertionSort именно за счет того, что его асимптотическая сложность O(n*log(n)), и это при достаточно большом n «компенсирует» сколько угодно большую константу этого алгоритма.
Для алгоритмов сортировок, основанных на сравнении элементов, доказано, что не может существовать алгоритма со сложностью лучшей, чем n*log(n).
А можно поподробней про доказательство? Т.е., понятно, что алгоритмов с лучшей асимптотикой пока не придумали, но интересно было посмотреть именно на формальное доказательство.
Т.е., понятно, что алгоритмов с лучшей асимптотикой пока не придумали
И не придумают, ведь доказано, что минимум это O(nlogn)
Правда есть алгоритмы которые работают за время O(n), вроде BucketSort и Radix Sort. Но они не могут отсортировать произвольный набор данных, а только определенный, заранее известный.
посмотреть именно на формальное доказательство
classes.soe.ucsc.edu/cmps102/Fall01/solutions7.pdf — Смотрите проблему N2
Ссылка умерла, но дело ее живет: https://web.archive.org/web/20120106013846/classes.soe.ucsc.edu/cmps102/Fall01/solutions7.pdf
Алгоритм сортировки постепенно «уточняет» необходимую перестановку так, чтобы в итоге осталась одна единственная, сортирующая именно эту входную последовательность. Здесь можно представить работу алгоритма как дерево принятия решений — на каждом шаге множество возможный перестановок «делится» на те, которые точно не подходят и те, среди которых есть искомая. Т.е., например, до первого шага алгоритма у нас есть N! вариантов, а после первого шага — t1,1 вариантов, и исключены t1,2 вариантов. Причем t1,1 + t1,2 = N!.. На втором шаге уже t1,1 делится на t2,1 и t2,2 так что t2,1 + t2,2 = t1,1 и т.д. В этом дереве каждый лист соответствует одной перестановке — следовательно, их N! штук. Дерево строго бинарно. Если h — высота этого дерева, значит, на i-м уровне дерева не более, чем 2^(i — 1) вершин. И всего вершин — не более 2^h. Так получается неравенство 2^h >= N!.. После логарифмирования обеих частей можно получить следующую цепочку: h >= log_2(N!) >= (N/2) * log_2(N/2). Т.е. высота дерева не может расти медленнее, чем N*log_2(N), получается, h = O(N*log_2(N)) — это и является нижней оценкой на высоту дерева.
Немного скомкано получилось, уж извините, но идея, надеюсь, понятна.
вижу грациозное применение формулы приближения Стирлинга, но остается не вполне ясно, почему предполагается ("дерево строго бинарно") что из одного шага сравнения "попарно различимой" пары, которых существует N*(N-1) (далее m) вариантов, алгоритм извлекает уточняющую информацию строго для того, что бы сократить пространство вариантов вдвое. (Хотя закостенелая программерская интуиция и подсказывает что это должно быть так, но математика протестует о превышении предположений)
Есть ведь бородатая задачка найти за два взвешивания одну из 9 монет более легкую. Условие у нас определенно только бинарно может ветвить алгоритм, но разве это гарантирует, что ТО куда оно ветвиться (совершаемые действия) при этом не представляет отсев например двух третей где не лежит нужная перестановка.
ряд П(a) для a = от m до m-N*logN (минимальное кол-во раз-сравнений которое мы предполагаем N*logN - перемножаются значения максимально несущую информацию из оставшихся комбинаций) в этом случае должен бы дать точнехонько N!
... но тогда (даже не вычисляя это численно) можно предположить, что ли зря Стирлинг так мучался?
Это я не к тому что не правильно, а к тому что неясно из краткого вашего пояснения почему это предполагается так. Если согласиться с тем что количество вариантов за шаг проверки уполовинивается в среднем еще проще, то с тем, что оно строго уполовинивается какую бы пару мы не сравнили - уже гораздо сложнее. Это бы означало, что любая пара делит множество пополам разными способами, и для этого в факториале должно бы присутствовать в качестве множителя 2**( N*logN) (очень дохрена двоек сомножителей - есть ли их там столько, сомнительно, хотя чувствуется можно как-то посчитать)
вижу что просто посчитать кол-во двоек в 255!
их там 7*1 + 6*2 + 5*4 + 4*8 + 3*16 + 2*32 + 1*64 = 247 штук,
а исходя из предположения должно быть 255*log(255) ~ 2038
если же взять 256! - то их стант больше всего на 8 штук,
так что в целом их видимо примерно всегда в ~ logN раз меньше чем должно бы быть, что бы делить "всегда пополам" NlogN способами, так что я бы сказал скорее "дерево чаще всего не строго бинарно" (если вообще близко к разбиению пополам)
Ну а на постскриптум, статья оригинал (во всяком случае анимация именно оттуда)- куда более широко отвечает на поставленный вопрос (и даже на русской вики всё понятно)=)
1. Подумайте, интересено ли будет пользователям читать вашу статью. Вы пишете в первую очередь для сообщества, а не для себя. Иначе зачем вообще это нужно?
2. Хорошо изучите материал. Если вы завели тему, будьте готовы поддержать разговор на неё.
3. Определите для себя цель написания статьи. Возможно, вы хотите рассказать сообществу о новом, малоизвестном алгоритме; возможно, собрать воедино и структурировать информацию о чём-то, чтобы другие люди могли прочитать одну статью вместо 2-х десятков противоречивых и устаревших страниц по теме; возможно, обоснованно высказать своё мнение. Но должна быть цель, некий посыл, с которым вы пришли.
У вас же получается статья о сортировке, которую все и так хорошо знают, анализ алгоритмов вы пока ещё не очень освоили и поддержать разговор на хорошем уровне ещё не получается, а цель статьи остаётся неясной. Сообщество старается селекционировать наиболее полезные и интересные материалы и отсеивать остальные, поэтому вас и минусуют. Создавайте хороший, полезный материал, и вас будут плюсовать ;)
В мире алгоритмов: Сортировка Вставками