恒定时间级联计算可能吗？

这是一个关于计算机技术限制的教育性的问题。
我有一个心态，下面的程序是不可能被创建的。恒定时间级联计算可能吗？

假设我必须开发一个累积统计数据结构。
下面是本说明书中： -

用户可以update(i,value)到data[i]在O(1)（平均情况）。
用户可以在O(1)（平均情况）下查询getAccu(i) = data[0]+data[1]+...+data[i]。
我不能以任何方式假定调用这两个函数的顺序。

这是我的代码（coliru demo）。
它并不虽然满足上述要求： -

#include <iostream> 
#include <vector> 
int data[5]={0,1,2,3,4}; 
int accu[5]={0,1,3,6,10}; 
/** assume that index always >=1 */ 
void update(int index,int value){ //O(n) i.e. O(array length) 
    data[index]=value; 
    for(int n=index-1;n<5;n++){ 
     accu[n]=accu[n-1]+data[n]; 
    } 
} 
int getAccu(int index){   //O(1) 
    return accu[index]; 
} 
int main(){ 
    update(2,12); 
    //note: data = 0,1,12,3,4 
    //  accu = 0,1,13,16,20 
    std::cout<<getAccu(3)<<std::endl; //16 
    //update() ... getAccu()... update() ... 
}

没有左右的内存存储和数据结构的类型大小限制，
是有可能使这两个函数update(index,value)和getAccu(index)是O(1)？

如果是，如何？如果不是，为什么？

对不起，这个隐晦的话题。我找不到更合适的一个。

来源

2017-10-08 cppBeginner

这与计算技术的局限性无关。它与多个连接变量的恒定时间更新的任意要求的限制有关。 – Peter

@彼得我想这可能是可能的，但是我们目前的研究还没有达到这一点。防爆。在Hash被发明之前的几天，几乎在每个操作中都不可能找到具有O（1）的通用数据结构。 ....我认为这是其中之一。 ....如果您仍然认为我使用了不正确的单词，请随时编辑它。谢谢。 :) – cppBeginner

使用某种树，你可以为两个操作做'log n'。然后，使更新懒惰，您可以检测到两个查询之间有很多更新并以不同方式处理它的情况。不变的时间似乎是乐观的。 –

在一段时间内做所有事似乎是乐观的。如果您不介意O(log n)的复杂性，则可以维护一个平衡的二叉树，在每个节点中存储以该节点为根的子树的总数。

更新一个值时，只需更新从根到该元素的路径中的log n小计。

计算累加器只是从根中找到正确的节点，并且每次向右添加左小计。

而不是急于进行更新，您可以将它们在恒定时间添加到待更新项目列表中，然后当您收到查询并且该列表不是空时，您可以执行每个更新log n或如果有许多更新，只更新O(1)中的值，并重新计算O(n)中的整个累加器，但如果在2个查询之间可能会获得许多更新，那么这样做只是值得的。

来源

2017-10-08 07:13:50

这是一个很好的答案，谢谢。你从哪里得到这个想法？这种酷技术有一个名字吗？我想了解更多。 – cppBeginner

不知道，在树中存储小计是一个相当标准的技术，但我没有具体的例子。 –

恒定时间级联计算可能吗？

回答

相关问题