Эквивалентные структуры данных с одинаковыми границами в худшем случае (в сравнении с амортизированными) - PullRequest
Новая
       45

Эквивалентные структуры данных с одинаковыми границами в худшем случае (в сравнении с амортизированными)

4 голосов
/ 01 февраля 2012

Я не мог сделать свой заголовок очень описательным, извиняюсь!

Является ли это случаем, что для каждой структуры данных, поддерживающей некоторые операции с определенным амортизированным временем выполнения, другая структура данных, поддерживающая те же операции в те же времена выполнения в худшем случае? Меня интересуют как итеративные, эфермальные структуры данных, так и функциональные.

Я уверен, что этот вопрос уже задавался раньше. Я не могу найти правильные ключевые слова для поиска (в Google, SO, TCS). Я ищу цитируемый ответ в {да, нет, открыто}.

1 Ответ

2 голосов
/ 01 февраля 2012

Нет, по крайней мере, в моделях, где различимость элементов из 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
...