有效遍历变更清单

Question

我有一个列表更改列表 - 添加和删除。这份名单可能很大 - 比如1000件。

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

我可以从头开始一直走到改变9'000。这对我来说似乎有点啰嗦。

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

但Big O表示将问题的大小减半并不会使事情变得更有效率（如果我理解正确的话）。

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

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

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

我的第一个想法是为每个id存储它所分配的事件以及它被解除分配的事件。然后把这个列表推到第一个分配事件大于9000的分配。但就像我说的那样，这只会减少我需要经过的项目数量。

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

Answer 1

如果你每隔Xth更改一次缓存列表的状态，那么你可以进行二进制切换以达到限制你正在寻找的更改的两个缓存状态，然后你最多走X个项目来获取项目本身。那是O（log N），或多或少。

但更一般地说，减少大O的复杂性是手段，而不是结束。如果您的列表通常是10,000个项目，那么无论是通过降低复杂性还是通过加快速度，您都应该担心N = 10,000的速度很快。

编辑：糟糕，我只是更仔细地阅读了您的问题。如果你每个（例如）100个项目缓存状态，你就不会搜索，所以你甚至不需要进行二进制搜索 - 你只需直接跳到最近的缓存状态并走最多100个项目来获取项目本身。那么这是一个恒定时间算法吗？

Answer 2

您正在使用哪种结构？没有一种有效的方法来处理通用数据结构，但是有数千种优化方法和特定结构的有效方法。

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

Answer 3

'时间戳'或标记每次插入和删除，然后通过简单的遍历来查找更改（O（n））。