アルゴリズムのステップ数を示す正確な関数を見つける

Question

int mystery(int n) { 
    int s = 0; 
    int tmp = n+1; 
    for (int i; i<=n; i++) { 
     s = tmp + i; 
     tmp = s; 
    } 
    return s; 
} 

この関数はどのようにして決定できますか？また、この機能は実行時間に関して改善することができますか？

Answer 1

上記には余分なコードがいくつかあります。 sは完全に不要です。それなしでそれを書き直すと、それはより明確になります。

int mystery(int n) { 
    int tmp = n + 1; 
    for (int i = 1; i<=n; i++) { 
     tmp += i; 
    } 
    return tmp; 
} 

何それがないこと4、次に3、次に2、その後1を追加

1 + Nに設定 tmp

• あるので

にこれは、現在の実行中の時間を持っていますO(n)。しかし、1 + 2 + 3 + ... + Nにはconstant time formulaがあることが判明しました。これを使用して、一定時間である以下を作成することができます。

int mystery(int n) { 
    int triangleNumber = (n * (n + 1))/2; 
    return triangleNumber + n + 1; 
}