2つのイテレーター変数を持つ配列の2つの半分をカバーする単一whileループのBig-Oh表記

Question

私のBig-O理解のテストをブラッシュアップしようとしている（明らかに必要な非常に基本的なBig-Oの理解）私の本でいくつかの練習問題をやっていた。

彼らは私に次のコード

public static void swap(int[] a) 
{ 
    int i = 0; 
    int j = a.length-1; 

    while (i < j) 
    { 
     int temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
     i++; 
     j--; 
    } 
} 

私が思うに理解するのは簡単を与えました。それは2つのイテレーターのそれぞれが一定量の作業量で配列の半分をカバーしています（これはO（n/2）の両方で計時すると思う）

したがって、O（n/2）+ O （2n/2）= O（n）

これは私の現在の理解であり、問​​題解決のための私の試みでしたので、許してください。私はbig-oオンラインの多くの例を見つけましたが、イテレータが基本的に同じ時間に配列を増分して修正するところは、これと全く同じです。

これはループが1つあるため、とにかくO（n）だと思うようになっています。

誰でも私のためにこれをクリアすることができますか？

おかげ

Answer 1

それは一つのループが私はそれがとにかくO（n）のだと思い作って持っているという事実。

これは正しいです。 1つのループを作っているわけではなく、定数の大きさによって配列のサイズに依存する1つのループであるため、big-O表記は定数を無視します。 O(n)は、アルゴリズムの影響がアレイのサイズに基づくことのみを意味します。その時間が実際には半分かかっていることは、ビッグオーには関係ありません。

つまり、アルゴリズムに時間がかかる場合n+X、Xn、Xn + Yはすべてbig-O O(n)になります。

ループの大きさが一定の係数以外の変更が、サイズが100、ループが2ある場合nの対数または指数関数として、例えば、サイズが1000であり、ループは3である場合は、異なる取得サイズは10000でループは4です。その場合は、たとえば、O(log(n))となります。

ループがサイズに依存しない場合も、これとは異なります。つまり、ループサイズに関係なく、常に100回ループする場合、アルゴリズムはO(1)（すなわち、一定の時間で動作する）になります。

また、私が正しい姿勢のどこかにあった方程式があるかどうかは疑問でした。

はい。実際に、数式がn * C + Yという形になると、Cが一定で、Yが他の値の場合、結果は1より大きいか、1より小さいかにかかわらず、O(n)になります。

Answer 2

あなたはループについて正しいです。 LoopはBig Oを決定しますが、ループの半分だけループが実行されます。

です。 2 + 6 *（n/2）

nを非常に大きくすると、他の数は実際には小さくなります。だから彼らは問題ではありません。 そのO（n）です。

2つの別々のループを実行しているとします。 2 + 6 *（n/2）+6 *（n/2）。その場合、再びO（n）になります。

しかし、ネストループを実行するとします。 2+ 6 *（n * n）。それから、O（n^2）になります。

常に定数を削除して計算します。あなたはその考えを持っています。

Answer 3

j-iが各繰り返しで2単位減少すると、N/2が取られます（N=length(a)と仮定）。

したがって、実行時間は実際にはO(N/2)です。 O(N/2)は、厳密にはO(N)に相当します。