Предложен алгоритм сортировки массива за линейное время. Теорема об n*log(n) опровергнута!
Два шнапса этому арийцу
04.02.2020, 10:15
Не, СталинСорт вообще должен работать за константное время. Вот примерная реализация алгоритма:
void StalinSort(std::vector& citizens) {
citizens.clear();
}
void StalinSort(std::vector& citizens) {
citizens.clear();
}
Бля, оно восприняло угловые скобки с типом, как тег. Кароче, в векторе был тип Kulak.
Тут такое дело, что если в математике теорема доказана без ошибок, опровергнуть это нельзя. Никак. Можно не надеяться.
Но можно обойти, изменив входные данные. Теорема верна лишь для алгоритмов построенных на основе попарного сравнения на однопроцессорной машине (одноленточной машине Тьюринга).
Radix O(n), хитрые модификации черпака O(n), сортировочные сети O(log n) работают быстрее. Во всяком случае в рамках математической абстракции.
Но можно обойти, изменив входные данные. Теорема верна лишь для алгоритмов построенных на основе попарного сравнения на однопроцессорной машине (одноленточной машине Тьюринга).
Radix O(n), хитрые модификации черпака O(n), сортировочные сети O(log n) работают быстрее. Во всяком случае в рамках математической абстракции.
С каждым годом понимать it и около it шутки становится все сложнее.
