Почему обычная сортировка O (n sqrt n) в среднем случае?

Question

Я нашел Strand sort очень привлекательным для сортировки односвязных списков в постоянном пространстве, потому что это намного быстрее, чем, например, сортировка вставкой.

Я понимаю, почему это O(n) вв лучшем случае (список уже отсортирован) и O(n^2) в худшем случае (список отсортирован обратно).Но почему O(n sqrt n) в среднем случае?Если алгоритм не основан на делении пополам и имеет полиномиальную производительность для наилучшего и наихудшего случаев, то в среднем случае просто O(n^m), где m - среднее арифметическое значений показателей для наилучшего и наихудшего случаев (m = (1 + 2) / 2 = 3/2, O(n sqrt n) = O(n^(3/2)))

Answer 1

Исходная ссылка на сортировку Strand: http://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 ... в соответствии с этим это O (n ^ 2). Strand sort был представлен как компонент J sort, который, как он утверждает, является O (n lg n). То, что средняя сложность равна O (n ^ 2), имеет смысл, поскольку в случайных данных половина нитей будет иметь длину 1, а O ((n / 2) ^ 2) = O (n ^ 2).

Answer 2

На странице Википедии, на которую вы ссылались, средняя производительность по случаю составляет O (n lg n) со ссылкой на эту страницу переполнения стека. Что странно, потому что нигде на этой странице это не сказано.

В любом случае, в дополнение к тому, что говорил Ульрих, анализ среднего случая сложен, потому что он должен учитывать, как данные представлены в среднем, что не является тривиальным.

Из Википедии:

Определить, что означает среднее значение ввода, сложно, и часто это среднее значение ввода имеет свойства, которые затрудняют математическую характеристику (рассмотрим, например, алгоритмы, предназначенные для работы со строками текста). Точно так же, даже когда возможно разумное описание конкретного «среднего случая» (которое, вероятно, будет применимо только для некоторых применений алгоритма), они приводят к более сложному анализу уравнений.