performance - 计算算法的 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 是我得出的结果，由此我推导出 O(n^2) 的大 O。我在计算中犯了什么错误，如果有的话......

编辑:...计算推导 T(n) 的原始操作？

Answer 1

你的结果 O(n^2) 是正确的，由两个嵌套循环给出。我更喜欢这样的推导

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

通过观察嵌套循环得出结论。