線形時間でバイナリ配列をソートする方法は？

Question

http://www.techiedelight.com/sort-binary-array-linear-time/

線形時間我々は、アレイ一つだけの時間を通過する必要があることを意味しますが、ここで解決策によると、我々は最初のゼロの数を見つけるために、配列を横断し、その後、我々は最初を埋めるために再びそれを通過配列の一部を0で、残りの部分を1で置き換えます。

だから、その線形時間の解はどうですか？ 何が欠けていますか？

Answer 1

で配列をソートの2倍以上の時間がかかります時間複雑線形時間はO(n)のように表されます。これは、入力のサイズに対して実行時間が直線的に増加することを意味します。この例では、配列の長さに比例した、配列のすべての要素を合計します。

は、具体的にあなたの例に、Sort()でこのループを見て：

int zeros = 0; 
for (int i = 0; i < n; i++) 
    if (A[i] == 0) 
     zeros++; 

このループはA[]て直線的に横断し、ゼロの量を合計します。リニア時間もこれらのループに適用されます。あなたは、単に一度A[]を横断していると

int k = 0; 
while (zeros--) 
    A[k++] = 0; 

// fill all remaining elements by 1 
while (k < n) 
    A[k++] = 1; 

。

これらの操作は、アレイが2回横断されるため、O(2n)です。したがって、関数Sort()はの操作であり、これはO(n)に相当します。

これは別の例です。 10バイナリ数に比べて100バイナリ数をソートしなければならない場合は、時間がかかりますか？この場合、100の2進数をソートすることは、10の2進数をソートすることよりも10倍長くなります。これは、入力のサイズに対して線形時間がが直線的に増加するためです。nです。

Answer 2

解決策では、配列は2回横断されます。したがって、注文はO(2n) = O(n)です。 Big-O表記は定数を無視します。 nおよび2nは両方とも、nの値で直線的に成長する。関数に定数を掛けたり追加したりしても、関数の振る舞いは変わりません。

Answer 3

「線形時間」は、アルゴリズムの必要とする時間がアレイのサイズに比例して増加することを意味します。ここでは、配列に追加するアイテムごとに、さらに2つの比較（2n）があります。

Answer 4

アルゴリズムは、その時間複雑さがO（n）ならば、線形時間、すなわちO（n）時間を取ると言われています。非公式には、これは、入力サイズが十分に大きい場合、実行時間は入力のサイズに比例して増加することを意味します。

このアルゴリズムは配列を2回横断するので。まだ線形です。線形方程式y = 2 * xを考える。

Answer 5

O（2n）、O（1221n）、O（n）、O（n/2）。これらはすべて線形です。それは、実行の時間が常に絶えず変化することを意味します。あなたが例えばサイズ10の配列を持っているのであれば、それは常にサイズ5.

Answer 6

共有されるすべての方法は、線形時間複雑度であり、つまりO(n)です。しかし、直接的/直接的に、彼らは配列の中で同じ要素を2回横断しており、Aquarius（The Asker）は一回通過法を探しています。次のコードでは、配列を1回走査して走査中にソートします。

int left = 0, right = arr.length - 1; 
while (left < right) 
    { 
     while (arr[left] == 0 && left < right) 
      left++; 

     while (arr[right] == 1 && left < right) 
      right--; 

     if (left < right) 
     { 
      arr[left] = 0; 
      arr[right] = 1; 
      left++; 
      right--; 
     } 
    } 

レコードについて、

O（C *のN）= O（N）、cは定数である