Вычисление T (n) временной сложности алгоритма

Question

Я ищу некоторые пояснения в разработке временной эффективности алгоритма, в частности, T (n).Алгоритм ниже не так эффективен, как мог бы быть, хотя я считаю, что это хороший пример для изучения.Буду признателен за построчное подтверждение суммы операций в коде:

Псевдокод

 1.  Input: array X of size n
 2.  Let A = an empty array of size n
 3.  For i = 0 to n-1
 4.      Let s = x[0]
 5.      For j = 0 to i
 6.          Let sum = sum + x[j]
 7.      End For
 8.      Let A[i] = sum / (i+1)
 9.  End For
 10. Output: Array A

Моя попытка расчетаT (n)

 1.  1
 2.  n
 3.  n
 4.  n(2)
 5.  n(n-1)
 6.  n(5n)
 7.  -
 8.  n(6)
 9.  -
 10. 1

 T(n) = 1 + n + n + 2n + n^2 - n + 5n^2 + 6n + 1
      = 6n^2 + 9n + 2 

Итак, T (n) = 6n ^ 2 + 9n + 2 - это то, что я получаю, из этого я получаю Big-OO (N ^ 2).Какие ошибки я допустил в своих вычислениях ...

Редактировать: ... при подсчете примитивных операций для получения T (n)?

Answer 1

Ваш результат O (n ^ 2) является правильным и задается двумя вложенными циклами.Я бы предпочел вывод типа

0 + 1 + 2 +  + (n-1) = (n-1)n/2 = O(n^2)

, который следует из наблюдения вложенных циклов.

Answer 2

Я не совсем уверен в вашей методологии, но O (n ^ 2) кажется правильным.На каждой итерации первого цикла вы выполняете цикл из предыдущих элементов.Поэтому вы смотрите на 1 в первый раз, 2 во второй, затем на 3, а затем ... на n в последний раз.Это эквивалентно сумме от 1 до n, которая дает вам сложность n ^ 2.