このプログラムのBig-OはO（N^2）ですか？

Question

私はCodi​​ng Interview（新しいCoding Interview）を読んでいます。プログラムが正しく動作しているようです。私がそれをチェックすると、N^2/2が答えと思われます。私は正しいとは思わない。 Big-Oが何で、なぜそうなのか誰かに教えてもらえますか？

class Program 
    { 
     static void Main(string[] args) 
     { 
      int userNumber = Convert.ToInt32(Console.ReadLine()); 
      int[] makeAnArray = new int[userNumber]; 
      for (var x = 0; x < userNumber; x++) 
      { 
       makeAnArray[x] = x; 
      } 
      DisplayIterations(makeAnArray); 
     } 
     static void DisplayIterations(int[] testA) 
     { 
      int totalIterations = 0; 
      for (var i = 0; i < testA.Length; i++) 
      { 
       totalIterations++; 
       Console.WriteLine("i is " + i); 
       for (var j = i + 1; j < testA.Length; j++) 
       { 
        totalIterations++; 
        Console.WriteLine("j is " + j); 
       } 
      } 
      Console.WriteLine("The amount of iterations: " + totalIterations); 
     } 
    } 

基本的機能は、アレイにかかるループlength-1の配列の長さおよびAのforループを実行します。私は10を入れて55を返します。

Answer 1

nは、配列のサイズである反復の実際の数は、次のとおりです：

(n^2 + n)/2

に

n(n+1)/2

を拡張することができ

この回答を参照してください。

ただし、Big O表記では、一般的ですアルゴリズムのクラスに興味があり、入力サイズが大きくなると、上記の式の2などの定数と最大の指数よりも小さな指数を無視することができます。したがって、n^2は0になりますので、nコンポーネントは無視してください。非常に迅速に非二次成分よりも大きく、nのサイズが大きくなります。したがって、実際の操作回数が(n^2 + n)/ 2のアルゴリズムをO（n^2）と呼びます。参考

、ここでWikipediaからランダウの記号の定義は次のとおり

ランダウの記号は、引数が特定の値または無限大に向かう傾向がある機能の制限動作について説明した数学的表記です。nを持っている理由の

説明（N + 1）/ 2の操作：

あなたは次のようにあなたのアレイを反復されています

for (var i = 0; i < arr.Length; i++) 
{ 
    for (var j = i + 1; j < arr.Length; j++) 
    { 
    } 
} 

私が行きますよ以下の表記といくつかの例を引き出す：

i0 means that your program printed out 'i is 0' 
j1 means that your program printed out 'j is 1' 

はのは、どのようなプログラムのwoulを引き出してみよう

i0 

今3の配列の長さ：

i0 j1 j2 
i1 j2 
i2 

各列は、外側ループの反復全体を表す1の配列の長さ、ならびに内部ループで印刷dは6の配列の長さ：あなたは簡単にこの方法でそれを引き出すことで見ることができますどのような

i0 j1 j2 j3 j4 j5 
i1 j2 j3 j4 j5 
i2 j3 j4 j5 
i3 j4 j5 
i4 j5 
i5 

たちは6 + 5 + 4 + 3 + 2つの+ 1文n = 6なお、これをプリントアウトしていることですジュ1から6まで、またはより一般的には1からnまでのすべての整数の加算。 1からnまでの整数の合計の一般的な公式は（驚き！）(n^2 + n)/2です。

私はこれを少し急いで入力しましたが、うまくいけば、私はこれにどのように到着したかを見てください。これは、長さ10の入力に対して、（10^2 + 10）/ 2 =（110）/ 2 = 55という反復があることに同意します。

Answer 2

はい、そのプログラムのBig-OはO（N^2）です。

Big-O表記では、支配的要因（係数無視など）のみを使用します。

実際の答えはn（n-1）/ 2ですが、もっと正確ではありますが、表記法は1/2の係数を無視します（&）。 Why do we ignore co-efficients in Big O notation?