Как правильно подсчитывать операции (временную сложность) в алгоритме пузырьковой сортировки в Python ⇐ Python

[Anonymous]

Это мой код:

Код: Выделить всё

def sort_bubble(list):
comp_counter = 0
swap_counter = 0
n = len(list)
for i in range(n-1):
for j in range(n-i-1):
comp_counter += 1
if list[j] > list[j+1]:
swap_counter += 1
list[j], list[j+1] = list[j+1], list[j]
return comp_counter, swap_counter

Необходимо выполнить пузырьковую сортировку списка, а затем вернуть необходимое количество операций (временная сложность).
Я запускал этот код в двух случаях (в каждом списке было 20000 чисел):
a) Сортировка уже отсортированного списка (лучший сценарий): Количество сравнений = 49995000 = n(n-1)/2< /сильный>; Количество свопов = 0. Мне кажется, здесь что-то не так, потому что количество сравнений в лучшем случае должно быть O(n), а количество свопов O(1) (для алгоритм пузырьковой сортировки).
b) Сортировка списка, отсортированного «обратно» (худший сценарий): Количество сравнений = 49995000 = n(n-1)/2; Количество свопов = 49993762. В худшем случае этот алгоритм должен иметь замены O(n^2) и сравнения O(n^2). Между тем количество свопов и сравнений ближе к O(n^2)/2
Для меня очевидно, что либо мой код, либо мое понимание временная сложность в алгоритмах полностью изношена. Наверное, и то, и другое. Кто-нибудь из вас, добрые джентльмены, объяснит, что я делаю не так?

Подробнее здесь: https://stackoverflow.com/questions/784 ... gorithm-in