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

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

Мой вопрос про то, что в предыдущей оценке у вас O(N^2) вы предпочли не заметить, ну что ж, ладно

Давайте я на всякий случай повторю ваши слова, чтобы не перепутать:

radix sort сортирует массив из N строк длины N за O(pN).

давайте я еще раз по-другому спрошу: чему в вашем случае равен p? Это явно не константа, т.к. иначе вы ее не стали бы показывать в O(p*N). Это не длина префикса двух случайных строк как в квиксорте, потому что она по моим же оценкам, меньше единицы. Если она зависит от N, какова формула этой зависимости?

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

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

Мой вопрос про то, что в предыдущей оценке у вас O(N^2) вы предпочли не заметить, ну что ж, ладно

Давайте я на всякий случай повторю ваши слова, чтобы не перепутать:

radix sort сортирует массив из N строк длины N за O(pN).

давайте я еще раз по-другому спрошу: чему в вашем случае равен p? Это явно не константа, т.к. иначе вы ее не стали бы показывать в O(p*N). Это не длина обшего префикса двух случайных строк как в квиксорте, потому что она по моим же оценкам, меньше единицы. Если она зависит от N, какова формула этой зависимости?