从给定算法计算Big-O

Question

我正在考试我的考试,其中一个问题是从给定的算法计算大o.去年的一个问题是:

---

T_compute(n) ? O(n)

算法:

void func2(const int n) {
   for (int i = 1; i <= n; i++)
      compute(i);
}

func2的时间复杂度是多少？T_func2(n)∈

---

现在解决方案说时间复杂度是

T_func2(n) ? O(n/2(n-1))

任何人都可以向我解释他们如何得到这个解决方案？

Answer 1

既然我们知道的复杂性compute(n)是O(n),我们可以,不失一般性,分析的复杂性func2(n)的假设下compute(n) = n,即

T_func2(n) ? sum_{i = 1 to n} compute(i) 
           = sum_{i = 1 to n} i
           = n(n+1)/2 

在最后一步中我们使用了这个求和规则.

现在,我们可以说T_func2 ? O(n(n+1)/2)(我会假设这n(n-1)是一个错字),但这只是O(n^2).