0

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

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 ответ 1

3

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

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

2
  • А почему, например, во внешнем цикле эта проверка осуществляется только 1 раз за весь цикл(4 значения + 1 проверка), а во внутреннем цикле для каждого значения делается проверка?
    – prostak
    13 ноя 2020 в 7:28
  • 1
    Ну так внешний цикл один раз пробегает свой диапазон, конец диапазона один раз проверяется. А внутренний цикл запускается n-1 раз, и каждый раз приходится проверять конец.
    – MBo
    13 ноя 2020 в 8:09

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.