Предложен алгоритм сортировки массива за линейное время. Теорема об n*log(n) опровергнута!
Подробнее
mathew W @mathew@mastodon.social I came up with a single pass O(n) sort algorithm I call StalinSort. You iterate down the list of elements checking if they're in order. Any element which is out of order is eliminated. At the end you have a sorted list. 2018/10/26 04:20:16
it-юмор,geek,Прикольные гаджеты. Научный, инженерный и айтишный юмор,программирование,алгоритмы,песочница,приколы для образованных даунов со знанием английского
Еще на тему
void StalinSort(std::vector& citizens) {
citizens.clear();
}
ampersand lt semicolon
Но можно обойти, изменив входные данные. Теорема верна лишь для алгоритмов построенных на основе попарного сравнения на однопроцессорной машине (одноленточной машине Тьюринга).
Radix O(n), хитрые модификации черпака O(n), сортировочные сети O(log n) работают быстрее. Во всяком случае в рамках математической абстракции.