131
правка
Изменения
→Сложность
В неоптимизированной реализации на каждой итерации внутреннего цикла производятся <tex> n - 1 </tex> сравнений, а так как внутренний цикл запускается также <tex> n - 1 </tex> раз, то за весь алгоритм сортировки производятся <tex> (n - 1)^2 </tex> сравнений.
В оптимизированной версии точное количество сравнений зависит от исходного массива. Но точно известноИзвестно, что их количество не меньше, чем количество обменов, и не больше, чем худший случай равен <tex> (n - 1)^*n/2 </tex> {{---}} максимальное количество сравнений для данной сортировки. Следовательно, <tex> T_1 = O(n^2) </tex>.
В итоге получаем <tex> T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) </tex>.
