Здравствуйте, CoderMonkey, Вы писали:


ylp>>Число сравнений символов для radix sortа O(N^2) (m считаем константой и не учитываем)

CM>На самом деле — O(p*N)
что такое "p" (это что, мое матожидание общего префикса при попарных сравнениях? как оно применимо к радикс сорту, который обрабатывает все символы?) и почему внезапно у нас radix sort работает теперь за O(p*N). Он по вашим же предыдущим выкладкам работал за O(N^2)

Автор: CoderMonkey
Дата: 06.11.18

?

Нормальный случай:
quick sort — O(N^2 * log N)
radix sort — O(N^2)

в любом случае: логику ваших новых рассуждений (очевидно, что старое сообщение содержит неверную оценку, теперь у нас внезапно radix sort массива N строк длины N работает за O(pN)! ).

CM>Сумеешь сам сравнить с O(p*N*LogN) и сообразить, что меньше, или тебе и в этом нужна помощь?
Мне не нужна ваша помощь, от вас скорее вред. Но чем дальше тем смешнее.