実行時間このアルゴリズムの実行時間は何ですか

for i=1 to n^2 
    for j=1 to i 
     // some constant time operation

私はO（N^4）を言いたいが、私は確信することはできません。これをどのように把握していますか？

2012-01-17 styfle

'はO（n^4）'。それはまた、（明らかではない） 'Θ（n^4）'です。 –

心配しないで、私は間違って計算しました。 – Rabbit

n^4が正しいです。 iはn^2まで直線的に上がり、（n^2）回実行されるため、内部ループは（n^2）/ 2回の平均実行時間を要します。

2012-01-17 00:33:28 bdares

ああ、欠けているリンクです：内側のループの平均時間は（n^2）/ 2です。ありがとう、それは理にかなっている。それはまた私が犯した数を確認します。 – styfle

あなたは正しいですか、それはN^4です。

置換を行うM = N^2今すぐあなたのループはこれに変更します。

for i in 0..M 
    for j in 0..i

これはO(M^2)あなたのよく知っている、したがって、結果は逆置換後O((N^2)^2) = O(N^4)です。

2012-01-17 00:36:20 dasblinkenlight

一定時間操作が実行されますので、それはあなたができる、それはΘ(n^4)だことを証明するには、明らかにO(n^4)

だ

n^2 + n^2 + ... + n^2  (n^2 adders) 
= n^2 * n^2 
= n^4

：未満である

1 + 2 + 3 + ... + n^2  (n^2 adders)

回liitleの数学を使用してください：

1 + 2 + 3 + ... + n^2 
= n^2 * (n^2 + 1)/2 
= n^4/2 + n^2/2 
>= n^4/2

2012-01-17 00:44:36

それはそれがO（n^4）であることを証明するのに理にかなっていますが、それが最も厳しい上限であるとは思わないと思います。 – styfle

いいえ、そうではありません。 –

アルゴリズムを解析するとき、上限が最も厳しい上限でない場合、上限を与えることはあまり役に立ちません。たとえば、アルゴリズムもO（n^5）とO（n！）ですが、実行時間の決定には役立ちません。 – styfle

-1

n^5 = outer * inner 
outer = n^2 
inner = n^2 + n^2-1 + n^2-2 +...1

2012-01-17 00:45:49

あなたの表記では、 'inner = 1 + 1 + ... + 1' –

ビッグオーの実行時間乗法を使用します。したがって、外側ループ（N^2）のビッグ・オーは内側（N^2）のビッグ・オと乗算されます。したがって、Big Ohは（N^2 * N^2）であり、同様の基底の指数を追加する方法を覚えていれば、N ^（2 + 2）またはN^4が得られます。シグマ表記を使用

2012-01-17 00:48:31

は、あなたは念入りな成長の順序を取得し終わる：

それは明らかである

enter image description here

2014-04-02 03:56:14

答えて