d
Ну radix sort-то за O(word_size*n). Если это по алгоритмам задание, то явно не это от тебя хотят)
word_size в битах?
Size: a a a
2020 June 01
SS
S
Ну radix sort-то за O(word_size*n). Если это по алгоритмам задание, то явно не это от тебя хотят)
Там вообще говоря всячески обходят вещественные числа и говорили что LowerBound сортировки чисел nlogn.
S
(но спросить стоило)
SS
Там вообще говоря всячески обходят вещественные числа и говорили что LowerBound сортировки чисел nlogn.
Это от рассматриваемой абстрактной модели машины зависит
S
Подумаю, может что-то упускаю. ( а ещё даты открытия алгоритмов посмотреть....)
d
Ну radix sort-то за O(word_size*n). Если это по алгоритмам задание, то явно не это от тебя хотят)
но в любом случае если данных будет достаточно много логарифм уступит
SS
Но в целом если это по CS задание, то лишние *word_size не прокатит
d
Но в целом если это по CS задание, то лишние *word_size не прокатит
cs?
SS
Computer science
d
Computer science
ааааа
SS
Но в целом если это по CS задание, то лишние *word_size не прокатит
Обратный Аккерман даже не прокатывает, который всегда меньше 5
I
Ну radix sort-то за O(word_size*n). Если это по алгоритмам задание, то явно не это от тебя хотят)
O(N) по итогу :)
I
Это ведь так считается...
d
O(N) по итогу :)
да, но это сильно влияет на условие при котором одно превосходит другое
I
да, но это сильно влияет на условие при котором одно превосходит другое
Ну radix в одном потоке - лучший вариант.
I
Решить задачу построения выпуклой оболчки в Рандомных условиях за On - вики мне не помогла: нету такого алгоритма у неё.
I
Но вот Грэхем, есть. И в Ieee754 получить O n, реально.
S
Я всё понимаю...
S
Но я наступил на грабли.