243
правки
Изменения
→Сложность: увеличение дробей
В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма <tex> T = T_1 + T_2 </tex>, где <tex> T_1 </tex> {{---}} время, затрачиваемое на сравнение элементов, а <tex> T_2 </tex> {{---}} время, за которое мы производим все необходимые обмены элементов.
Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве <texdpi=150> \frac {n (n - 1)} {2} </tex>. Получаем, что <tex> T_2 = O(n^2) </tex>.
В неоптимизированной реализации на каждой итерации внутреннего цикла производятся <tex> n - 1 </tex> сравнений, а так как внутренний цикл запускается также <tex> n - 1 </tex> раз, то за весь алгоритм сортировки производятся <tex> (n - 1)^2 </tex> сравнений.
В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен <texdpi=150> \frac {n (n - 1)} {2} </tex>, а лучший {{---}} <tex> n-1 </tex>. Следовательно, <tex> T_1 = O(n^2) </tex>.
В итоге получаем <tex> T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) </tex>.
