algorithm - 高效遍历变更列表

Question

我有一个列表更改列表 - 添加和删除。列表可能很大——比如 10,000 项。

我想知道更改 9'000 后列表的状态。

我可以从一开始就遍历列表以更改 9'000。这对我来说似乎有点啰嗦。

我可以保留一个项目列表并记录它们何时被添加和何时被删除，然后遍历此列表以查看列表中特定更改的内容。如果添加和删除的可能性相同，我将需要遍历的列表元素数量减半......

但是大 O 表示法表示，将问题的大小减半并不能提高效率（如果我理解正确的话）。

我可以在每 100 次或第 1000 次更改时缓存列表的状态……但是，大 O 再次表示，将项目数除以“n”并不能提高效率。

那么这样做的有效方法是什么？有没有一种有效的方法来做到这一点？

更多细节： 具体来说，我正在跟踪自定义分配器中的内存分配/释放。每个分配/解除分配都是列表中的一个事件。每个分配都有一个唯一的 ID。我想知道（例如）9'000 个事件之后当前分配的内容。

我的第一个想法是为每个 id 存储分配的事件和解除分配的事件。然后将此列表遍历到分配事件大于 9000 的第一个分配。但是就像我说的，这只会使我需要遍历的项目数量减半。

我喜欢 Mike F 提出的观点——从最近的第 100 个项目步行是恒定的时间......

Answer 1

如果您在每第 X 次更改时缓存列表的状态，那么您可以进行二进制切割以降低到限制您正在寻找的更改的两个缓存状态，然后您最多步行 X 个项目以到达项目本身。这或多或少是 O(log N)。

但更一般地说，降低大 O 复杂性是手段，而不是目的。如果您的列表通常包含 10,000 项，那么您应该担心在 N=10,000 时使其快速，无论是通过降低复杂性还是通过使其更快。

编辑：哎呀，我只是更仔细地阅读了你的问题。如果您每（例如）100 个项目缓存一次状态，那么您就不会进行搜索，因此您甚至不需要进行二进制切割 - 您只需直接跳转到最近的缓存状态并最多步行 100 个项目即可到达该项目本身。所以这是一个恒定时间算法，不是吗？

Answer 2

您正在使用哪种结构？没有一种有效的方法来遍历一个通用的数据结构，但是对于特定的结构有成千上万的优化方法和有效的方法。

是的，如果你有一个 O(n) 时间复杂度的算法，将项目数量减半不会改变它的 O(n) 复杂度......但这意味着每个新项目只有一半的效果原来有。大 O 表示法是一种对算法进行分类的好方法，但它并没有真正提高效率，除了大量的数字（一个很好的例子是排序。在最坏的情况下，快速排序比合并排序更复杂......但你可以实现快速排序除了处理数百万个项目的排序之外，几乎所有应用程序都比合并排序更有效）

Answer 3

'时间戳'或标记每个插入和删除，然后只需简单的遍历即可找到更改（O（n））。