algorithm - 在最坏情况下具有相同边界的等效数据结构（与摊销相比）

Question

我无法使我的标题非常具有描述性，抱歉！

对于每个支持某些摊销运行时间的操作的数据结构，在最坏的情况下，另一个支持相同运行时间的相同操作的数据结构是这样吗？我也对迭代的、短暂的数据结构和功能性的数据结构感兴趣。

我敢肯定，这个问题以前一定有人问过。我似乎找不到正确的搜索关键字（在 Google、SO、TCS 中）。我正在{是，否，打开}中寻找引用的答案。

Answer 1

不，至少在n 个元素的元素区别需要时间 Ω(n log n) 的模型中。

考虑以下我使用 Python 描述的数据结构。

class SpecialList:
    def __init__(self):
        self.lst = []
    def append(self, x):
        self.lst.append(x)
    def rotationalsimilarity(self, k):
        rotatedlst = self.lst[k:] + self.lst[:k]
        count = sum(1 if x == y else 0 for (x, y) in zip(self.lst, rotatedlst))
        self.lst = []
        return count

很明显append，并且rotationalsimilarity（因为它清除了列表）摊销 O(1)。如果rotationalsimilarity是最坏情况 O(1)，那么我们可以提供一个 O(1)undo操作，将数据结构恢复到之前的状态。因此，我们可以在 O(n) 时间内实现元素区别。

def distinct(lst):
    slst = SpecialList()
    for x in lst:
        slst.append(x)
    for k in range(1, len(lst)):  # 1 <= k < len(lst)
        if slst.rotationalsimilarity(k) > 0:
            return False
        slst.undo()
    else:
        return True