4

タイトルをうまく説明できませんでした。申し訳ありません。

すべてのデータ構造について、特定の償却された実行時間でいくつかの操作をサポートし、最悪の場合、同じ実行時間で同じ操作をサポートする別のデータ構造があるということですか? 反復的で一時的なデータ構造と関数型のデータ構造の両方に興味があります。

私は、この質問が以前に尋ねられたにちがいないと確信しています。正しい検索キーワードが見つからないようです (Google、SO、TCS で)。{yes, no, open} で引用された回答を探しています。

4

1 に答える 1

2

いいえ、少なくとも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に and rotationalsimilarity(リストをクリアするため) は O(1) に償却されます。最悪の場合O(1) の場合、データ構造を以前の状態に復元するrotationalsimilarityO(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
于 2012-01-31T23:56:04.703 に答える