вычислительная сложность функции

Question

У нас есть домашнее задание написать псевдокод, который сортирует массив от наименьшего до самого большого. это то, что я писал:

Function sorting(list) 
;define 
index = 0 
for i in list.length: 
    ;take first element from unsorted part in array 
    small = list[0+i] 
    ;length of unsorted list 
    for n in list.length-i: 
     ;runs on all elements in list starting from unsorted part (i) 
     if list[n+i] <= small: 
      ;if it is smallest, take smallest place 
      small = list[n+i] 
      ;save it's index 
      index = n+i 
    put where the smallest is, the first element in unsorted part 
    list[index] = array[i] 
    ;put in first place of unsorted the smallest. we actually exchange smallest with first 
    array[i] = small 
return list 

так что для первого цикла, я п раз, что в нем,

п (1 + ....)

но второй цикл, то всегда становится меньше, я понятия не имею, как вычислить его.

пожалуйста, помогите

Ps, мне не нужен большой о, я знаю, что это O (n²), мне нужна формула сложности

Answer 1

Это O (N^2).

Возможно, вам захочется изучить различные алгоритмы сортировки, например quicksort, mergesort, heapsort и bubblesort.

Answer 2

Ваше приблизительное количество шагов: n + (n-1) + (n-2) + ... + 1. Это равно n * (n + 1)/2. С точки зрения сложности это O (n^2), или, естественно, число элементарных операций пропорционально квадрату входного размера.