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

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

ylp>>Мой вопрос про то, что в предыдущей оценке у вас O(N^2) вы предпочли не заметить, ну что ж, ладно
CM>Все зависит от того, какие операции считать. Если тебе так хочется считать посимвольно, то у квиксорта для тех же данных получается O(N^2 * log N)
У квиксорта посимвольно получется O(p*N*logN), потому что квиксорт сравнитвет только общие префиксы строк.

CM>Ты правда не понимаешь или просто изображаешь полного идиота из каких-то странных соображений?
извините, но идиотом во всем этом треде выглядите как раз вы


ylp>>Это не длина обшего префикса двух случайных строк как в квиксорте, потому что она по моим же оценкам, меньше единицы.
CM>О, вечер становится по настоящему томным. Каким образом ты насчитал меньше единицы для алфавита в 256 символов и 1000 строк?
Прочитайте внимательно мой ответ. p это матожидание длины общего префискса двух случайно выбраных из N строк. Квиксорт проводит O(N*LogN) сравнений пар строк. И да, сюрприз — для 1000 строк на алфавите из 256 смиволов p будет меньше единицы. Это значит что две случайно выбранные сроки скорее всего вообще не будут иметь общий префикс.


ylp>>давайте я еще раз по-другому спрошу: чему в вашем случае равен p?
CM>То же самое — средняя длина одинакового префикса.
Ну ладно, давайте поиграем в эту игру дальше. Чему по вашему равен p? Зависит ли он от размера алфавита и от N?