Bin*_*Bin 5 algorithm data-structures
我有一个家庭作业问题如下(请注意,我不是在寻找确切的答案,只是寻找简单的建议继续前进).
S是在时间<= T(n)中支持Insert(x,S),Delete(x,S)和Find_Smallest_Item(S)的数据结构.证明T(n)的下界,例如Ω(logn).
到目前为止,我的想法是:
我想我需要找到一个减少,我将把这个问题简化为一个更简单的问题,并证明它不能低于logn.我阅读了许多关于下界的教程,其中大多数将问题简化为排序,然后他们使用排序作为黑盒子并证明算法不能低于nlogn.
但是在这里,我们正在处理logn,我不知道这样的算法要减少到.也许它必须对树结构的深度做一些事情,登录.但我无法弄清楚从哪里开始.
你能给我一些提示吗？
编辑:其实我想到了一些东西,但我不知道我是否应该用这样的伎俩证明一个下限.所以,我假设我有insert,delete和find_smallest操作,每个操作都有一个logn时间复杂度.
例如,要构造一个排序列表,我可以使用delete和find_smallest函数,例如我可以第一次运行find_smallest,并在找到列表中的最小元素后,然后我将删除该元素.我将再次运行它,因此我将找到第二个最小的元素,依此类推.
因此,我可以使用delete和find_smallest函数实现排序.因此,如果我继续这样做n次,它们中的每一个都将记录(删除)+ logn(用于查找最小值),因此总体而言,排序将采用nlogn.
不过,我不知道如何调整它以进行插入.
编辑2:为了使用插入证明:在列表中找到第i个最小元素后,如果我将其插入第i个位置怎么办？例如,在通过上述过程找到第3个最小元素之后,我可以将其插入数据结构的第3个索引.因此,最后我将获得一个排序的数据结构.
将您的问题减少到另一个问题将为您提供O()的上限,而不是较低的上限.
另一方面,如果您可以使用任何解决问题的方法来实现具有众所周知的下限的其他算法(有效地将该问题减少到您的问题),那么这可能会为您提供所需的下限.
回答:
正如其他人所建议的那样,您可以使用数据结构S来实现排序:
for i in range(input):
Insert(S, input[i])
for i in range(input):
x = Find_Smallest_Item(S)
output[i] = x
Delete(S, x)
对于大小为N的输入,此算法对您的三个操作中的每个操作进行N次调用.但是,我们知道任何通用排序算法必须具有O(N log N)的最坏情况.
这意味着将存在以下类型的数据结构调用的平均时间为每次调用O(log N)的情况.由于这与任何T()渐近地与log N不相容,因此您具有下限.
一些说明:
您的问题中描述的数据结构类型称为优先级队列.
由于您试图证明任何可能的优先级队列的下限,因此您无法对实现进行假设.仅仅因为特定的数据结构为您提供了特定的O()性能,并不意味着某些完全不同的数据结构不可能更好.
有许多优先级队列数据结构满足所有调用的O(log N),因此这实际上是一个紧密的下限.
您的第一次编辑不正确。
我可以第一次运行 find_smallest ，在找到列表中的最小元素后，
运行时会找到SFind_Smallest_Item(S)中的最小元素，而不是列表中的最小元素。在找到任何内容之前，您首先需要插入（列表中的元素，S）！
也许您应该尝试写一些代码，如下所示：
List l = [1,25,4,3,7]
S S // empty
List sorted // empty
//now we can do:
insert(l[0],S)
//or
delete(25,S)
//magic goes here
...
//and l is sorted!
诀窍是写下对 l 进行排序的代码（或生成另一个排序列表）。为了证明下限，计算步骤（插入、删除和查找）并利用这样一个事实：无论您编写什么代码，它都不能（最坏情况）比O(nlogn)（用于比较排序）更快。这给出了一个下限，它必须至少这么慢。