1

誰かが私にこのコードをくれたので、正確な複雑さを見つけるか、言い換えれば、特定のnがLの計算方法を知るための式を見つけると思います。

L = 0;
for (i = 1; i<n; i++)
    for (j = 1; j<i; j++)
        for (k = j; k<n; k++)
            L++;

私の最初の考えは（n ^ 3 + n ^ 2）/ 2でしたが、間違っています。

たとえば、n = 5 L = 20; n = 10 L = 240

ありがとう

編集：この問題は、アルゴリズムの基礎、140ページまたはPDFのスライド161からのものです（これは無料の本のバージョンです） http://www.freebookspot.es/Comments.aspx?Element_ID=76025

4

2 に答える 2

2

これは数学であり、プログラミングではありません。

Lは次のようになります（Sはビッグシグマ、合計）：

    n-1   i-1   n-1
   S     S     S    1
   i=1   j=1   k=j

   n-1 i-1
= S   S  (n - j)
  i=1 j=1

   n-1 i-1      n-1 i-1
= S   S  n  -  S   S  j
  i=1 j=1      i=1 j=1 

       n-1          n-1 
= n * S   (i-1) -  S   (i-1)i/2
      i=1          i=1

等々。n最初の整数n(n+1)/2の合計がであり、最初のn二乗の合計がであるということを知る必要がありn(n+1)(2n+1)/6ます。で3次方程式になりnます。

私はもう学部生ではないことを指摘してくれたBarmaleyの答えのおかげで、数式を操作して単純化する必要がなくなりました。WolframAlphaが私に代わってやってくれます;-)

答えはn(n-1)(n-2)/3です。通常、これらのことがうまく因数分解されると、長い表現をあまり多く書かずに答えを出すために、私が早い段階で作成できた重要な洞察（おそらく幾何学的な洞察）があることがわかります。この結果は、側面がn、、、の直方体に内接するピラミッドのボリュームのように不審に見えます。n-1n-2

于 2013-02-06T17:50:27.020 に答える
2

第一に、複雑さはnの具体的な数ではありません。それは漸近的な振る舞いについてです。アルゴリズムの複雑さがO（f（n））であると言っても、アルゴリズムが厳密にf（n）演算を実行するという意味ではありません。実際、それは2*f(n)または1/2 * f(n)またはを行うことができますf(n) + sqrt(f(n))。複雑さについて話すとき、通常、入力の増加に伴って操作の数がどれだけ速く増加するかに関心があります。

あなたの場合、3つのネストされた合計（ループごとに1つ）と内部操作の合計コスト（1と仮定）を記述する必要があります。

プロセス

そして、これは正確な式です（私を信じないでください— wolfram | alphaを使用して確認してください）が、複雑な言語では、O（n ^ 3）になります。

UPD：この式less-or-equalは、単なる。ではなく、タイプの条件を持つループに対応していることに注意してless-thanください。

于 2013-02-06T17:58:44.567 に答える