与えられたアルゴリズムからBig-Oを計算する

Question

私は現在、質問の1つが与えられたアルゴリズムからbig-oを計算する私の試験のために勉強しています。

---

T_compute(n) ∈ O(n) 

：アルゴリズム：昨年からの質問の一つは次のようになります

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

関数func2のtimecomplexityは何ですか？ T_func2（N）∈

---

今ソリューションは、時間の複雑さが

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

であることを述べている誰もが、彼らがこの溶液になったか私に説明できますか？

Answer 1

我々はO(n)するcompute(n)の複雑さを知っているので、我々は、一般性を失うことなく、私たちがきた最後のステップでそのcompute(n) = n、すなわち

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

仮定の下func2(n)の複雑さを分析することができますused this summation rule。

ここでT_func2 ∈ O(n(n+1)/2)と書いてありますが（n(n-1)はあなたのためにタイプミスです）、これはちょうどO(n^2)です。