Вообщем мелкие массивы он сортирует со скоростью вставками, т.е. за n операций, для больших массивов (больше 64), его асимптотика равна асимптотике сортировки слияние, т.е. за nlogn. А значит тут вообще говорить о том, что алгоритм работает с такой же скоростью в асимптотике, что и сортировка бинарного дерева, не корректно.
В статье говорят об алгоритмах, а не о реализации алгоритма на каком либо языке. К примеру, есть такая вещь как хвостовая рекурсия. Она реализована не во всех языках, но она существует и она не требует памяти для хранения точки возврата из функции в стеке, возврата не происходит.
Если какой-то язык не реализует что-то необходимое для реализации алгоритма, это ещё не значит что алгоритм работает медленно или использует больше места.
Что-то я не понял, это в асимптотике тимсорт в лучшем случае работает за O(n)?
Странно, лично мне показалось, что на лучшем наборе он работает за такое время только, когда используется сортировка вставками (ибо последовательность может быть уже отсортирована, тогда вставки работают за O(n)) значит она может работать с O(n) только до minrun, до дальше работает слияние, но слияния, в свою очередь, будут работать в лучшем случае O(nlogn) значит и весь алгоритм в асимптотике будет работать за O(nlogn). Так что я ставлю под сомнение вообще достоверность всей таблички в статье, и не правомерно сравнивать алгоритмы для которых асимптотики написаны не верно — «левые»…
К примеру, мне интересно, а зачем нужна память в быстрой сортировке? Я раньше думал, что не нужна, ибо сортировка идёт «на месте».
Затем, я думал, что в лучшем случае, для сортировки слиянием потребуется память O(n), конечно если не использовать Алгоритм Пратта (точно не помню как его зовут, может и не Пратт) или другие методы связанные с медианами (асимптотика которых написана на третьей строке таблицы), значит уже 3 ошибки в таблице. Причём одна из них связанна с повествуемым материалом, который сравнивается с методом сортировки бинарным деревом, у которого коэффициенты у сложности намного больше даже чем у сортировки слиянием (ибо приходится уравновешивать дерево, а иначе он будет работать не быстрее быстрой сортировки на плохом случае, т.е. за O(n^2))
«На таких данных Timsort рвёт в клочья все остальные алгоритмы. » — конечно конечно, если считать что он асимптотически на лучшем наборе работает за O(nlogn), коих результатов не может добиться ни один алгоритм (сарказм).
dl.dropbox.com/u/5753856/%D1%81%D0%BA%D1%80%D0%B8%D0%BD2.png
dl.dropbox.com/u/5753856/%D1%81%D0%BA%D1%80%D0%B8%D0%BD1.png
dl.dropbox.com/u/5753856/%D1%81%D0%BA%D1%80%D0%B8%D0%BD1.png
Первый скрин страница 198, второй скрин страница 219
Его анализ идёт в рамках данного языка, да, в C/C++ нет средств (хотя я не знаю) оптимизации к хвостовой рекурсии на уровне компилятора, поэтому для данных языков это верно.
ru.wikipedia.org/wiki/%D0%A5%D0%B2%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
См. раздел «описание». Примечание: причём возрат в функции это void.
Если какой-то язык не реализует что-то необходимое для реализации алгоритма, это ещё не значит что алгоритм работает медленно или использует больше места.
Странно, лично мне показалось, что на лучшем наборе он работает за такое время только, когда используется сортировка вставками (ибо последовательность может быть уже отсортирована, тогда вставки работают за O(n)) значит она может работать с O(n) только до minrun, до дальше работает слияние, но слияния, в свою очередь, будут работать в лучшем случае O(nlogn) значит и весь алгоритм в асимптотике будет работать за O(nlogn). Так что я ставлю под сомнение вообще достоверность всей таблички в статье, и не правомерно сравнивать алгоритмы для которых асимптотики написаны не верно — «левые»…
К примеру, мне интересно, а зачем нужна память в быстрой сортировке? Я раньше думал, что не нужна, ибо сортировка идёт «на месте».
Затем, я думал, что в лучшем случае, для сортировки слиянием потребуется память O(n), конечно если не использовать Алгоритм Пратта (точно не помню как его зовут, может и не Пратт) или другие методы связанные с медианами (асимптотика которых написана на третьей строке таблицы), значит уже 3 ошибки в таблице. Причём одна из них связанна с повествуемым материалом, который сравнивается с методом сортировки бинарным деревом, у которого коэффициенты у сложности намного больше даже чем у сортировки слиянием (ибо приходится уравновешивать дерево, а иначе он будет работать не быстрее быстрой сортировки на плохом случае, т.е. за O(n^2))
«На таких данных Timsort рвёт в клочья все остальные алгоритмы. » — конечно конечно, если считать что он асимптотически на лучшем наборе работает за O(nlogn), коих результатов не может добиться ни один алгоритм (сарказм).