Сложность сортировки выбором

Вот есть функция сортировки выбором:

def SelectionSort(A):
    for i in range(len(A) - 1):
        minimum = i
        for j in range(i + 1, len(A)):
            if A[j] < A[minimum]:
                minimum = j
        A[i], A[minimum] = A[minimum], A[i]
    return A
list2 = [5, 4, 3, 2, 1]
SelectionSort(list2)
print(list2)

и по идее ее сложность равна О(n^2), т к во втором цикле for число повторов равно сумме(n - i + 1) от i=1 до i=n-1 (+ 1, т к цикл как бы еще раз повторяется, но не выполняется). И по идее для пяти элементов эта сумма равна 11. Но line profiler почему то выдает 14, хотя дальше все идет как надо. Почему line profiler отображает 14, а не 11? Заранее спасибо.

P.S И объясните, пожалуйста, почему именно n - i + 1? То есть насчет единицы я понял, но почему n - i? На примерах я проверил и вроде бы действительно так. Но хотелось бы понять именно теоретически, чтобы не приходилось потом придумывать разные примеры и постоянно считать. Еще раз спасибо.

Line #      Hits         Time  Per Hit   % Time  Line Contents


==============================================================
 2                                           def SelectionSort(A):
 3         5         73.0     14.6     30.8      for i in range(len(A) - 1):
 4         4         17.0      4.2      7.2          minimum = i
 5        14         60.0      4.3     25.3          for j in range(i + 1, len(A)):
 6        10         43.0      4.3     18.1              if A[j] < A[minimum]:
 7                                                           minimum = j
 8         4         22.0      5.5      9.3          A[i], A[minimum] = A[minimum], A[i]
 9         1         22.0     22.0      9.3      return A

Process finished with exit code 0


Ответы (1 шт):

Автор решения: MBo

Строчка с for срабатывает 5+4+3+2 = 14 раз
Для i = 0 тело цикла исполняется 4 раза, и ещё один раз проверяется, что аргумент стал равен 5
То же самое и для дальнейших действий

почему n - i? потому что на i-м обороте внешнего цикла i элементов уже обработано, осталось n-i

→ Ссылка