0

こんにちは、これは試験のレビューからの質問です。次のコードフラグメントの実行時間（Big-O）を見つける必要があります。

sum = 0; 
for( i = 0; i < n; i++ ) 
 for( j = 0; j < i * i; j++ ) 
  for ( k = 0; k < j; k++ ) 
    ++sum;

O（n ^ 4）だと思います。最も内側のループはnまで実行され、2番目のループはn ^ 2まで実行され、最も外側のループはn回実行されます。よろしくお願いします

4

3 に答える 3

3

いいえ、O（4）ではありません。

これを確認するためのより良い方法は、ループが実行される回数を数えることです（実際、それがコードが実行していることです）。

sum（sum（sum（1、k = 0..j）、j = 0..i * i）、i = 0..n）

= sum（sum（j、j = 0..i * i）、i = 0..n）= sum（i * i *（i * i + 1）/ 2、i = 0..n）これはn ^ 5のオーダーであるsum（i ^ 4、i = 0..n）のオーダー。

基本的に、真ん中のループはi * iであり、最も内側のループごとに実行されているため、余分な時間をカウントする必要があります。

C++では

http://codepad.org/nKJ9IUnt

1 0
2 0
3 6
4 42
5 162
6 462
7 1092
8 2268
9 4284
10 7524
11 12474
12 19734
13 30030
14 44226
15 63336
16 88536
17 121176
18 162792
19 215118

このテーブルを使用して、結果が定数または0になるまで有限差分（導関数を取る）を計算できます。定数リストを作成するには、5つの導関数が必要であることがわかります。これは、リストがn^5のオーダーであることを意味します。

たとえば、2つの要素間の各差が定数であるリストがある場合、リストは線形関数で表すことができます。差の差が一定の場合、それは四分円などになります（低次の項は導関数/差によって変換されるため、問題ではありません）

于 2013-03-12T03:10:31.727 に答える
1

正式には、シグマ表記を使用すると、成長の順序を鋭い精度で推測するのに役立ちます。

ここに画像の説明を入力してください

于 2014-04-14T12:30:54.427 に答える
0

あなたは簡単に考えることができます：

In the first loop: i = n
second loop: j = i*i => j = n^2
third loop: k = j => k = n^2
So, the bigO = n * n^2 * n^2 = n^5
于 2014-05-16T03:46:36.453 に答える