algorithm - O(1) 固定サイズ配列の最小値

Question

私は32個の数字を持つ配列を持っています。最初は、すべての数値は 0 ですが、おそらく重要ではありません。

いつでもこの配列の 1 つの数値を変更できます。

このような更新後に、最小値とそのインデックスをすばやく見つけたいと考えています。O(1)時間でそれを行う方法はありますか?

Answer 1

サイズ32の配列で行うほとんどすべてはですO(1)。線形スキャンには32の比較が必要です。O(1)

O（1）=一定の操作数。配列のサイズが32（または問題の固定サイズ）の場合、操作の数は確かに一定です（このように考えてください：線形スキャンをループの代わりに連鎖if条件に置き換えることができます：
if (arr[0] < min), if (arr[1] < min) , ... if (arr[31] < min)

そのスリルのために、サイズの配列の一般的なケースに関しては、n比較ベースのアルゴリズムでは不可能です。
もしそうなら、O(n)比較ベースのアルゴリズムを使用してソートできます。

given an array A:
max <- max(A)
build an empty data structure as desired let it be `S`.
for each element of A - insert it into S in a different index.
while (S.min() <= max):
   idx <- S.findminIndex()
   print S.min()
   S.update(idx,max+1)

上記のアルゴリズムの各操作がO(1)であり、ループが何度も繰り返されると仮定すると、比較ベースの並べ替えが問題であることが証明されているためn、アルゴリズムはAO(n)を並べ替えることができません。Omega(nlogn)

Answer 2

O（1）アルゴリズムを提供することはできません。これは、最小ヒープを使用して更新を実行し、でO(log n)最小値を見つけるための1つの良い方法かもしれませんO(1)。小さいサイズのアレイの最小ヒープは十分に高速であり、更新のパフォーマンスはごくわずかです。