0 
for i <- 1 to n 
  for j <- i to n
    for k <- i to j

2 番目のループの実行時間の数式は何ですか?

n = n^2 の j = 1 から n までの合計ですか?

i と n の両方に依存しているため、どのように導出しますか?

4

1 に答える 1

1

2 つの方法で問題に取り組みましょう。

1.解決策

2 番目のループ実行時関数を計算する必要がある場合は、 と の両方の関数として表現する必要がありnますi。したがって、i定数として 2 番目のループに入り、2 番目または 3 番目のループのどこでもその値を変更しないため、 を修正します。i2 番目のループの実行時間が と の両方に依存する理由を確認したい場合は、同等の形式でアルゴリズムを記述できますn。

for i <- 1 to n 
   doSomething(i,n)


  doSomething(i,n):
    for j <- i to n
     for k <- i  to j
       doStuffHere() //

とが 1 回だけ実行されるとj=i、ループは 1 回の繰り返しで停止します。doStuff()j=ik=j=i

j=i+1、doStuff()を 2 回実行した場合など

jの任意の値に対して、doStuff()が実行される(j-i+1)回数、つまり の場合は 1 回、 の場合j=iは 2 回、 の場合j=i+1は 3 回j=i+3、...、j=i の場合は n-i+1 回というルールを導き出すことができます。つまり、実行時間関数は次のとおりです。

f(n,i) = 1+2+3+...+(n-i+1) = (n-i+1)*(n-i+1+1)/2 =
       = (n-i+1)(n-i+2)/2

後で、アルゴリズム全体の複雑度関数を導出しようとすると、1 から n までの各 i に対して f(n,i) があることがわかりますdoStuff()。したがって、アルゴリズム全体の実行時間は次のようになります。

RT(n) = f(1,n) + f(2,n) + f(3,n) + .. + f(n,n)

ここでいくつかの計算を行い、進行の合計に式を使用する必要があります。ただし、はるかに洗練された別のアプローチがありますが、理解するのが難しい場合があります。

2.解決策

アルゴリズムのすべての j と k について、次のことが明らかです。

  • i <= j,k <= n

  • k >= j

    したがって、コードが実際に行うことは、[i,n] (j<=k) から 2 つの正の整数 j と k を選択することです。これらのペア j,k を含むセットは、実際には繰り返しのある n-i+1 個の要素から 2 つの要素を選択する繰り返しのある組み合わせです。一部の選択肢では、最初の数値が 2 番目の数値よりも小さくならないため、混乱しないでください。いつでもそれらを切り替えることができます。つまり、降順以外で書き直してから、最初のものを j 、2 番目のものを k と見なします。これらの 2 つの数値は (n-i+1)(n-i+2)/2 の方法で選択でき、それがアルゴリズムの実行時間関数です。より多くのことを考え、エラーが発生しにくい数学計算を行うことで、はるかに洗練された方法でソリューションを得ることができます。アルゴリズム全体の実行時間関数を決定しようとすると、同じロジックが適用されます。

    数式との便利なリンク

  • http://en.wikipedia.org/wiki/Combinations

  • http://en.wikipedia.org/wiki/Arithmetic_progression
  • 他にもリンクはありますが、私はここの新しいユーザーなので、10 の評判ポイントを獲得する前に 2 つ以上のハイパーリンクを投稿することは許可されていません。: )
于 2013-01-17T14:30:36.060 に答える