Вот есть функция сортировки выбором:
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