algorithm - 变化的固定大小数组中的 O(1) 最小值

Question

我有一个包含 32 个数字的数组。最初，每个数字都是 0，尽管它可能并不重要。

我可以随时更改此数组中的一个数字。

我想在这样的更新后快速找到最小值及其索引。有没有办法在 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)

令人兴奋的是，对于 size 数组的一般情况，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次数，您的算法对 A 进行排序O(n)- 这是无法完成的，因为基于比较的排序被证明是有Omega(nlogn)问题的

Answer 2

我不能提供 O(1) 算法，可能是使用最小堆的一种好方法，O(log n)在O(1). 小尺寸数组的最小堆足够快，更新的性能可以忽略不计。