algorithm - O(n) ランタイムでの配列のソート

Question

メモリに関する制約がない場合、特定の配列を O(n) で重複してソートするアルゴリズムはありますか?

Answer 1

場合によります。下限と上限の両方（および最大精度/値の長さ）で入力を何らかの方法でバインドできる場合は、基数ソートを使用できますO(n). 同様に、バケット ソートO(n)は最良の場合でも複雑になる可能性がありますがO(n^2)、悪い入力の場合は悪化します。

ただし、一般に、入力をバインドできず、比較ベースの並べ替えを使用する必要がある場合は、それO(n log n)が最適であることを証明できます。

固定精度整数または浮動小数点数 (通常は最大 64 ビット) をソートする場合、値は効果的に制限され、基数ソートが可能になります。

値の最大ビット長が制限されている場合でも、ビット長が長いほど、定数は大きくなります。実際、並べ替える n 個の値があり、各値の長さまたは精度が最大 m ビットである場合、アルゴリズムの複雑さは O(nm) になります。

Answer 2

はい。スペースの複雑さに関する制限がない場合は、配列を o(n) 時間の複雑さでソートできます。

• k (k =10) 要素の配列があるとします。

• そして（みましょう）あなたの配列は次のとおりです：N [2,6,4,4,1,1,9,5,2,2]

• さて、私たちの考慮事項として、スペースに関する制限はありません。

• サイズ p の 2 次元配列 (temp_number[i][j]) があり (理論的には、p は無限であると見なされます)、インデックス i に何らかのフラグが含まれ、インデックス j にリンク リストが含まれているとします。

ここで、配列 N のすべての要素が temp_number[ ][ ] のインデックスに配置されるように temp_number[ ][ ] を埋め、フラグ = 1 にし、それ以外の場合はフラグ = 0 を保持します。

temp_number[0][1] = [1][1->1->null]
 temp_number[1][1] = [1][2->2->2->null]
 temp_number[2][1] = [0][3->null]
 temp_number[3][1] = [1][4->4->null]
 temp_number[4][1] = [1][5->null]
temp_number[5][1] = [1][6->null]
temp_number[6][1] = [0][null]
temp_number[7][1] = [0][null]
temp_number[8][1] = [1][9->null] & so on...

• これで、単一のループでflag=1を持つすべての要素を取得できます。

• ここでは、このようにしているのではないことに注意してください

  if(number1 > number2) { //ソートロジック... }

  したがって、ここではループが1 つしかないため、複雑度 0(n) を取得できます。