Сложность времени сортировки вставки и выбора Когда в массиве есть только два значения ключа

Question

Недавно я рассматриваю Алгоритм, 4-й Редактор sedgewick, и сталкивался с такой проблемой и не могу ее решить.

Проблема выглядит следующим образом:

2.1.28 Равные ключи. Сформулируйте и подтвердите гипотезы о времени выполнения вставки Сортировка сортировки и выбор сортировки для массивов, которые содержат только два значения ключа, при условии, что значения одинаково вероятны.

Объяснение: У вас есть n элементы, каждый из которых может быть 0 или 1 (без ограничения общности), и для каждого элемента x: P(x=0)=P(x=1).

Любая помощь будет приветствоваться.

Answer 1

сортировать Выбор:

Трудоемкость будет оставаться такой же (как это без предположения 2 ключа), он не зависит от значений массивов, только количество элементов ,
Временная сложность для выбора рода в этом случае O(n^2)

Однако, это справедливо только для оригинального алгоритма, который сканирует весь хвост массива для каждой внешней итерации цикла. если вы оптимизируете его, чтобы найти следующий «0», на итерации i, так как вы уже «очистили» первые i-1 нулей, то первое нулевое местоположение находится в индексе 2i. Это означает, что каждый раз внутренний цикл должен выполнять итерации 2i-(i-1)=i+1.
Подводя это будет:

1 + 2 + ... + n = n(n+1)/2 

Который, к сожалению, до сих пор в O(n^2).

Другой оптимизацией может быть «remmber», где вы остановились в последний раз. Это значительно улучшит сложность до O(n), так как вам не нужно проходить один и тот же элемент более одного раза - но это будет другой алгоритм, а не сортировка сортировки.

вставки Сортировать:

Здесь все сложнее. Следует отметить, что во внутреннем цикле (взятой из wikipedia), количество операций зависит от значений:

while j > 0 and A[j-1] > x 

Однако напомним, что в то вставки, после i-й стадии, первые i элементы сортируются. Поскольку мы принимаем P(x=0)=P(x=1), среднее значение i/2 элементов равно 0, а i/2 - 1.
Это означает, что средняя временная сложность для внутреннего цикла равна O(i/2).

Суммируя это вверх поможет вам:

1/2 + 2/2 + 3/2 + ... + n/2 = 1/2* (1+2+...+n) = 1/2*n(n+1)/2 = n(n+1)/4 

Вышесказанное, однако, до сих пор в O(n^2).

---

выше не является формальным доказательством, поскольку он неявно использует E(f(E(x)) = E(f(x)), что не так, но он может дать вам руководящих принципов, как формально построить ваше доказательство.

Answer 2

Ну, вы должны только искать, пока не найдете первый 0, при поиске следующего smmalest. Например, в сортировке сортировки вы просматриваете массив, который ищет следующее самое маленькое число для замены в текущую позицию. Поскольку есть только 0 и 1, вы можете остановить сканирование при встрече с первым 0 (поскольку это следующее минимальное число), поэтому нет необходимости продолжать сканирование остальной части массива в этом цикле. Если 0 не найден, сортировка завершена, так как «несортированная» часть - все 1s.

Вставка сортировка в основном такая же. В этом случае они оба O (N).