131
правка
Изменения
→Сложность
В неоптимизированной реализации на каждой итерации внутреннего цикла производятся <tex> n - 1 </tex> сравнений, а так как внутренний цикл запускается также <tex> n - 1 </tex> раз, то за весь алгоритм сортировки производятся <tex> (n - 1)^2 </tex> сравнений.
В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен <tex> \frac {n (n-1)*} {2} </tex>, а лучший {{---}} <tex> n/2 -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>.
