時間の複雑さのためのアルゴリズムを分析する

Question

私はアルゴリズムを分析しています。正しいトラックにいるかどうかを知りたいだけです。

このアルゴリズムでは、***が入っている行の乗算を数えています。ここで

はアルゴリズムだ：私は最も内側のラインから始めていますので、

1. 、私はそこに2つの操作（2つの乗算）がある見ることができます。
2. 今、私は内側の2つのループを調べているので、p=p*20*zが正確に(j) + (j-1)+(j-2)+(j-3)...1回実行されるとわかります。これはj(j+1)/2と等しくなります。
3. 合計で2つの乗算があるので、2 * (j(j+1)/2)が発生します。
4. 最後に、 "i"ループは正確にn回発生するので、合計でn(2 * (n(n+1)/2))です。

これは私の考えのプロセスです。私は正しいですか？ありがとう。

Answer 1

あなたの思考プロセスは正しいです。 j項をn（nは、jがとりうる最大の値）に置き換える必要がありますが、それはおそらくタイプミスです。

また、あなたはあなたがどこからさらに簡素化することができます：

n(2*(n(n+1)/2)) 
2*n*(n^2+n)/2 
n^3+n^2 

=> O(n^3) 

のn乗の項は、nが、我々はそれを支配すると言うことができます用語乗よりもはるかに大きな速度で成長するので、最後のステップがあります大きなnの実行時間。私が言及する他の点は、店舗を2つの操作だけでなく操作としてpと考えるべきであるということですが、これは単純にbig-oランタイムを変更しないことは明らかです。基本的には

1. i <= n
2. j <= n
3. k <= j

：あなたはすべての3つのループが同じ終了条件up to nを持っていることを知ることができれば、この特定の例では

Answer 2

計算を簡略化することができ3番目のループはのように繰り返されます。そうk <= n、 これはその複雑さを意味する。これは、あなたが念入りあなたのアルゴリズムの成長の順序を得ることができる方法であるn * n * n = O(n^3)

Answer 3

次のようになります。