私はこれらのJava関数のBig-Oをどのように誤解していますか？

Question

最初の例では、これは次のようになりました。O（n）、理由はわかりません。

例1：第二例えば

for (k = 0; k <= n/8; k++) // will be O(n/8) thus, O(n) 
    System.out.println(k); // will be O(n) 
System.out.println("Hello World!"); // will be O(1) because not in a loop 
for (p = n; p >= 1; p--) // will be O(n-1) thus, O(n) 
    System.out.print(p % 2); // not sure what % will do here, but I think it's still O(n) 
    // Overall I think it's O(n) 

。これはO（n^2）であることが分かりました。

例2：第例えば

for (k = 0; k < n - 1; k++) // will be O(n-1) or O(n) 
    for (m = k + 1; m < n; m++) // will be O(n^2) because nested loop 
     System.out.println(k * m); // not sure what this will do but I think it will be O(n^2) 
    // Overall I think it's O(n^2) 

、これはO（N）であることが判明したが、なぜわかりません。

例3：

for (i = n - 3; i <= n - 1; i++) { // not sure here, maybe O(n-1), thus O(n) 
    System.out.println(i); // since it is nested then O(n) 
    for (k = 1; k <= n; k++) // since this is the second loop, then O(n^2) 
     System.out.println(i + k); // not sure what this will do, but I think it will be O(n^2) 
} // Overall I think it's O(n^2) 

は最後の例は、理由がわからない、また、O（N^2）であることが判明しました。

Example4：

for (a = 1; a <= n/3; a++) // will be O(n/3) thus O(n) 
    for (b = 1; b <= 2 * n; b++) // since it's a nested loop it will be O(2n^2) thus O(n^2) 
     System.out.println(a * b); // not sure what this will do, but I think it will be O(n^2) 
    // Overall I think it's O(n^2) 

誰かがこれらを読みと私が間違っているのかを説明してもらえます。私の推論は、ユーザーが入力したものであり、その成長の仕組みを見ているので、 'n'変数を追跡するということです。単一のステートメントの場合、O（n^2）のネストされたループ内にある場合、そのループはデフォルトでO（n）である場合、定数時間O（1）です。

あなたの例1、2の推測と4はあなたのソリューションに等しいので はあなた

Answer 1

ありがとう助けてください、私はあなたがをよく見ると、あなたが唯一の例3.

に問題があると仮定しています最初の行はfor (i = n - 3; i <= n - 1; i++)で、n-3からn-1（両端を含む）になるので、nの値には依存しません。

for (i = n - 3; i <= n - 1; i++) { // O(3), so O(1) (since it'a a constant factor) 
    System.out.println(i); // nested, O(1) 
    for (k = 1; k <= n; k++) // O(n) 
     System.out.println(i + k); // nested, so O(n) 
} // Overall O(n) 

Answer 2

まず、あなたの推論は正しいようです。

たとえば、1、あなたはnまで繰り返します。 Big O表記法では、ランタイムの複雑さが何に限っているかだけを気にします。従って、2nはnとなるので、O(n)となる。

例2の場合、実行時の複雑さはnより大きくなります。これは基本的にはnに達するまで繰り返され、各反復中に反復回数に達するまで繰り返します。したがって、n以上ですが、n^2未満です。しかし、Big Oは上限ですので、O(n^2)と書き留めてください。

たとえば、最初のforループでcloseループを実行します。 nが何であれ、ブロック内にあるものは4回だけ実行されます（これは一定の時間です）。入れ子にされたforループは、例1のように、したがってO(n)です。

たとえば、最初のforループはO(n)です（あなたの言ったように、O(n/3)はO(n)になります）。ネストされたforループはほとんど同じです。 O(n*2)はO(n)になります。したがって、それはO(n^2)です。

Answer 3

それぞれの例を見て、時間の複雑さの背後にある理由を説明しよう。

あなたの例：

for (k = 0; k <= n/8; k++) // will be O(n/8) thus, O(n) 
    System.out.println(k); // will be O(n) 
System.out.println("Hello World!"); // will be O(1) because not in a loop 
for (p = n; p >= 1; p--) // will be O(n-1) thus, O(n) 
    System.out.print(p % 2); // not sure what % will do here, but I think it's still O(n) 
    // Overall I think it's O(n) 

説明：我々は最初のループがn回を実行し、第二のループはn回実行されることを見るので
これはO（n）があります。複雑さを計算すると、これはO(n + n) => O(2n)になります。ここでは、「無関係」（< =それらはまったく関係ないわけではないので、単にそれらを数えないため）定数を削除するという答えを簡略化しています。

あなたの例：

for (k = 0; k < n - 1; k++) // will be O(n-1) or O(n) 
    for (m = k + 1; m < n; m++) // will be O(n^2) because nested loop 
     System.out.println(k * m); // not sure what this will do but I think it will be O(n^2) 
    // Overall I think it's O(n^2) 

説明：
は今、私たちはn回を実行し、外側のループ、およびn回を実行し、内側のループを持っています。つまり、合計時間はO(n*n) => O(n^2)です。それはかなり自明です。

あなたの例：

for (i = n - 3; i <= n - 1; i++) { // not sure here, maybe O(n-1), thus O(n) 
    System.out.println(i); // since it is nested then O(n) 
    for (k = 1; k <= n; k++) // since this is the second loop, then O(n^2) 
     System.out.println(i + k); // not sure what this will do, but I think it will be O(n^2) 
} // Overall I think it's O(n^2) 

説明：
ループの最初は、あなたのループがnの値に依存しないn - 3からn - 1に実行されているので。だから我々は唯一O(n)

あなたの例を作る内部ループを数える：

for (a = 1; a <= n/3; a++) // will be O(n/3) thus O(n) 
    for (b = 1; b <= 2 * n; b++) // since it's a nested loop it will be O(2n^2) thus O(n^2) 
     System.out.println(a * b); // not sure what this will do, but I think it will be O(n^2) 
    // Overall I think it's O(n^2) 

説明：
これと上記のコードの違いは、このforループの外にはnの値に依存していることです。 nが成長するにつれて、n/3もこれがそれO(n^2)ます。n - 3とn - 1とは対照的に、（成長します。