O（1）最小在一个固定大小的数组中变化

我有一个32位数组的数组。最初，每个数字都是0，但它可能并不重要。O（1）最小在一个固定大小的数组中变化

在任何时候我可以改变这个数组中的一个数字。

我想快速找到这样的更新后的最小值及其索引。有没有办法在O（1）时间做到这一点？

来源

2012-08-15 user16367

您可以登录你同时想什么，当你在阵列中更改数字？ – irrelephant 2012-08-15 10:03:19

几乎你在32位数组上做的每件事都是'O（1）'。线性扫描需要32个比较，它在'O（1）' – amit 2012-08-15 10:04:37

@amit中。在决定算法是否为O（1）时，数组的大小并不重要。对具有32个值的数组进行线性扫描不是O（1）。 – user16367 2012-08-15 10:11:44

几乎你在32号数组上做的所有事情都是O(1)。线性扫描需要32个比较，这是在O(1)

O（1）=常数ops。如果数组的大小为32（或者对于这个问题有任何固定的大小），ops的数量确实是不变的（想想这样：你可以用一个链条代替线性扫描来取代线性扫描：
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次，你的算法能对一个在O(n) - 这不能做，因为基于排序comparations被证明是Omega(nlogn)问题

来源

2012-08-15 10:20:04 amit

不幸的是，我认为这使得感觉，这是不可能的。 – user16367 2012-08-15 10:27:13

我不同意你的术语，但我明白你的观点。大哦表示法是考虑运行时间/空间随问题大小的变化。在这种情况下，对于大小为n的数组，线性扫描需要O（n）操作。对于给定的n，它会像你指出的那样保持不变。 – brain 2012-08-15 10:29:15

最后upvoter（和@ user16367）：这是我的第1000个算法的upvote。我希望明天能够获得算法的金牌徽章，并成为第二个SO用户来赢得它。谢谢！:) – amit 2012-08-15 10:42:07

我不能提供一个O（1）算法，可能是一个很好的方法是使用最小堆，在O(log n)中做更新，并在O(1)中找到最小值。对于小尺寸阵列，最小堆速度足够快，并且在更新中的性能可以忽略不计。

来源

2012-08-15 10:19:19

是的，这将是我的最后手段 – user16367 2012-08-15 10:20:53

我怀疑如果在输入没有限制的情况下可以找到更好的选项，还要注意'log n'太小而且比太多具有大常数因子的线性算法。 – 2012-08-15 10:22:46

O（1）最小在一个固定大小的数组中变化

回答

相关问题