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

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

ylp>>Чтобы в массиве из миллиона строк каждая строка начиналась на разный символ, размер алфавита должен быть равен миллиону.

CM>Да, начинаешь немного соображать. Именно поэтому я написал "идеальный" и "реальный" случай отдельно.
CM>Что-нибудь ответить по существу можешь?
Конечно могу, но начинает уже быть лень. Так уж и быть, объясняю для тупых, в последний раз.

Посколько с "идеальным" случаем вы уже глубоко сидите в луже, давайте разбирать случай реальный. В реальных случаях у нас есть размер алфавита, который будет у нас для определенности m. И есть реальные строки на этом алфавите. Я принципиально не буду уточнять. что такое "реальные строки", пусть будут просто случайные наборы символов.

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

число сравнений символов для quick sortа — O(p*N*LogN), где p — среднее число символов, которые нужно сравнить в рамках одной операци сравнения двух строк, которую делает quicksort, т.е. длина общего префикса двух сравниваемых строк.

будем оценивать p:

у нас есть массив из N строк каждая длины N на алфавите m.

Если каждая строка — это случайная перестановка N элементов алфавита размером m, матожидание размера общего префикса для двух строк равно
(1-m^(-N)) / (m-1) (см https://math.stackexchange.com/questions/1782644/longest-common-prefix-among-n-strings-with-length-k) — т.е. оно околонулевое. Это значит что на случайном наборе строк при попарном их стравненнии в среднем мы обработаем меньше одного символа. Можете убедиться в этом, нагенерировав случайных строк длины 1000 на с m=256 (1 байт) и посравнивав случайные пары из них — у них в среднем почти никогда не будет общего префикса.

Что еще вам оценить, сомневающийся вы наш? Может, провести тот же анализ для длинных строк, являющихся случайными предложениями на человеческом языке? или сами догадаетесь какая там ситуация с матожидаие длины общего префикса?