algorithm - 更新有序数组的最快方法是什么？

Question

我需要计算一维直方图，该直方图必须动态维护并经常查找。我的一个想法是用数据保留一个有序数组(因为这样我可以确定 O(1) 中的百分位数，这足以快速找到一个直方图，其中包含不均匀的 bin，每个 bin 内的点数完全相同)。

那么，有没有一种方法可以在 O(N) 以内将一个数字插入有序数组并保持有序？

我想答案是众所周知的，但我对算法知之甚少(从事数值计算的物理学家很少这样做)。

Answer 1

在一般情况下，您可以使用更灵活的树状数据结构。这将允许在 O(log) 时间内访问、插入和删除，并且也相对容易从库中获取现成的(例如:C++ 的 STL 映射)。

(或 HashMap ...)

带二分查找的有序数组做的事情和树一样，但更严格。对于访问和内存使用来说，它可能会更快，但如果必须在中间插入或删除东西(O(n) 成本)，你会付出代价。

但是请注意，有序数组对您来说可能就足够了:如果您的数据点通常相同，您可以维护一个对列表 {key, count}，按键排序，能够快速添加另一个实例现有项目的(但仍然需要做更多的工作来添加新项目)