Как стать автором
Обновить
0
Карма
0
Рейтинг

Пользователь

  • Подписчики
  • Подписки

Алгоритм сортировки Timsort

Мой феил, согласен с этим. Действительно асимптотика сложности снизу равна P(n) для всех n.

Алгоритм сортировки Timsort

Алгоритм сортировки Timsort

Для тех кто не в танке :)) выложу скрины со страниц Кормена, вынудили, обращаю внимание на второй скрин в нём говорится о реализации Седжвика…
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

Алгоритм сортировки Timsort

Седжвик пишет про реализации алгоритмов на C/C++… Реализацию алгоритма на некотором языке.
Его анализ идёт в рамках данного языка, да, в 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.

Алгоритм сортировки Timsort

Вообщем мелкие массивы он сортирует со скоростью вставками, т.е. за n операций, для больших массивов (больше 64), его асимптотика равна асимптотике сортировки слияние, т.е. за nlogn. А значит тут вообще говорить о том, что алгоритм работает с такой же скоростью в асимптотике, что и сортировка бинарного дерева, не корректно.

Алгоритм сортировки Timsort

В статье говорят об алгоритмах, а не о реализации алгоритма на каком либо языке. К примеру, есть такая вещь как хвостовая рекурсия. Она реализована не во всех языках, но она существует и она не требует памяти для хранения точки возврата из функции в стеке, возврата не происходит.
Если какой-то язык не реализует что-то необходимое для реализации алгоритма, это ещё не значит что алгоритм работает медленно или использует больше места.

Алгоритм сортировки Timsort

Что-то я не понял, это в асимптотике тимсорт в лучшем случае работает за O(n)?
Странно, лично мне показалось, что на лучшем наборе он работает за такое время только, когда используется сортировка вставками (ибо последовательность может быть уже отсортирована, тогда вставки работают за O(n)) значит она может работать с O(n) только до minrun, до дальше работает слияние, но слияния, в свою очередь, будут работать в лучшем случае O(nlogn) значит и весь алгоритм в асимптотике будет работать за O(nlogn). Так что я ставлю под сомнение вообще достоверность всей таблички в статье, и не правомерно сравнивать алгоритмы для которых асимптотики написаны не верно — «левые»…
К примеру, мне интересно, а зачем нужна память в быстрой сортировке? Я раньше думал, что не нужна, ибо сортировка идёт «на месте».
Затем, я думал, что в лучшем случае, для сортировки слиянием потребуется память O(n), конечно если не использовать Алгоритм Пратта (точно не помню как его зовут, может и не Пратт) или другие методы связанные с медианами (асимптотика которых написана на третьей строке таблицы), значит уже 3 ошибки в таблице. Причём одна из них связанна с повествуемым материалом, который сравнивается с методом сортировки бинарным деревом, у которого коэффициенты у сложности намного больше даже чем у сортировки слиянием (ибо приходится уравновешивать дерево, а иначе он будет работать не быстрее быстрой сортировки на плохом случае, т.е. за O(n^2))

«На таких данных Timsort рвёт в клочья все остальные алгоритмы. » — конечно конечно, если считать что он асимптотически на лучшем наборе работает за O(nlogn), коих результатов не может добиться ни один алгоритм (сарказм).

Информация

В рейтинге
Не участвует
Зарегистрирован
Активность