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

Question

start = 0
while (start!= len(array)-1):
    for i in range(start +1,len(array)):
            if (array[i]<array[start]):
                    array[i],array[start] = array[start],array[i]
                    print(array)
    start += 1

в этом случае сложность не должна быть такой, как O (n) = n * [(n-1) + (n-2) + .... (n- (n-1))]что касается каждого из n раз внешнего цикла, то внутренний цикл выполняется для шагов дифференциала, постепенно уменьшающихся на единицу.Таким образом, O (n) становится (n ^ 3 - n ^ 2) / 2.Что не так с моим подходом .?enter code here

Answer 1

Посмотрите на это так. Первый раз (start = 0) внутренний цикл выполняет n-1 шагов, во второй раз (start = 1) внутренний цикл выполняет n-2 шагов и так далее. Таким образом, у вас есть:

(n-1) + (n-2) + ... + 1 шаг, что равно (n ^ 2-n) / 2 шага.