複雑さがアルゴリズムネストされました

Question

私は現在データ構造コースを勉強しています。 以下のアルゴリズムの複雑さは正当化する必要がありますが、解決方法はわかりません。

for(int i=0;i<N;i++) 
    for(int j=0;j<i;j++) 
    for(int k=0;k<j;k++) 
     sum++; 

Answer 1

それぞれの複雑なステップを理解できるように、各行の下にコメントします。それが最も加重変数であるため、O（N^3）になり3（N^2）+ 4（N^3）あなたが3（N）の複雑方程式を与える

for(int i=0;i<N;i++)   //C(N) + C(N) + C(N) -> 3C(N) 
    for(int j=0;j<i;j++)  //C(N)(N) + C(N)(N) + C(N)(N) -> 3C(N^2) 
    for(int k=0;k<j;k++)  //C(N)(N)(N) + C(N)(N)(N) + C(N)(N)(N) -> 3C(N^3) 
     sum++;    //C(N)(N)(N) -> C(N^3) 

+あなたの方程式に。