2つのコードフラグメントのBig O表記

Question

私は2つのコード断片と、どのBig Oカテゴリに該当するのか説明しています。しかし、私のように試してみてください。私はそれを見たり、サンプルを実行したりすることで、何が出てくるのか説明することはできません。

最初：この

long count = 0; 
long n = 1000; 
long i, j, k; 
    for(i = 0; i < n; i++) 
     for (j = 0; j < i * i; j++) 
      for (k = 0; k < j; k++) 
       count++; 

サンプルの実行には、一貫して私を与えるN^4、私は与えられてきた答えは、jが同じ大きさ可能性がある、I^2と同じ大きさにすることができます」ですN^2であり、kはjと同じ大きさであり、N^2である。したがって、実行時間はN^N^2^N^2に比例する。これはO（N^5）である。

スニペット：

long i, j, k; 
long n = 1000; 
long count = 0; 
for (i = 1; i < n; i++) 
    for (j = 1; j < i * i; j++) 
     if (j % i == 0) 
      for (k = 0; k < j; k++) 
       count++; 

これについては、「if文は実行されていますdをN3回まで、前の議論で求めることができますが、O（N^2）回だけ真です（これはiごとに正確にi回になるためです）。したがって、最も内側のループはO（N^2）回だけ実行されます。 O（j^2）= O（N^2）時間が経過するたびに、O（N^4）の合計が得られます。

これはN^4 （しかし、私はN^4/10の結果を得ていますが）モジュロ計算は各i毎に真であるだけですが、ループに入るのはずっと少なくなっています。

？誰もが、私は最初のもののために

Answer 1

を理解していないよ何を明確にすることができます：

sum from i = 0 to n-1 of 
    sum from j = 0 to i*i-1 of 
     sum from k = 0 to j-1 of 
      1 

我々は1の合計を知っています倍mに等しいので、我々は我々が合計1 + 2 + ... + m = m * (m + 1)/2を知っているので、我々はさらに減らすことができます

sum from i = 0 to n-1 of 
    sum from j = 0 to i*i-1 of 
     j 

にこれを減らすことができます：私たちは外で(1/2)を取ることによって、これは容易に行うことができます

sum from i = 1 to n-1 of 
    (i * i - 1) * i * i/2 = (1/2) * (i * i * i * i - i * i) 

を合計してからi * i * i * iとi * iという用語を分割します。しかし、合計はi単独の場合よりもまだ難しく、あまり知られていません。それはTheta(n^5)であり、したがってO(n^5)であることが分かります。なぜこのことが判明したのか直感的な感覚を得るには、n^4の順番の差f(n+1) - f(n) = (1/2)(n^4-n^2)があることを認識しているので、fが連続関数であり、この差が導関数であれば、fの次数は1になります。 0, i, 2i, ..., (i-1)i：jは現在最も内側のループの目的のためにのみi異なる値をとること

sum from i = 0 to n-1 of 
    sum from j = 0 to i-1 of 
     sum from k = 0 to i*j-1 
      1 

注：第二ケースについて

。内部ループは、jのカウンタ値のi倍の回数だけ実行されます。私たちは通常の数学的結果を使うことができるように、「ステップ」表記を導入しないように、この乗算をシフトします。

sum from i = 0 to n-1 of 
    sum from j = 0 to i-1 of 
     i*j 

sum from i = 0 to n-1 of 
    i * (1/2) * i * (i - 1) = (1/2)(i * i * i - i) 

ここでも、これはTheta(n^4)であることが判明したと推測カンニングや計算を行うか、我々は（正しく）に再び私たちの直感を使用することができます。