小编Bin*_*Bin的帖子

免责声明:是的,这是一个家庭作业,我正在思考它几天但却找不到路要走.

所以有n条直线(y = ax + b),我想找到它们的上部包络线(图中的粗体部分).它必须在O(nlogn).

我的理解是,我需要找到一种方法来忽略一些行,因为如果我搜索所有行,它将不是O(nlogn).

我正在考虑分而治之的方法,以便我可以将列表分成两部分并递归地继续直到解决方案.但后来我不知道如何摆脱一些线路.很明显,我不需要考虑图片中的一些底线,因为他们不可能为解决方案做出贡献.但是我没有想到任何事情.任何提示都表示赞赏.

我有一个家庭作业问题如下(请注意,我不是在寻找确切的答案,只是寻找简单的建议继续前进).

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个索引.因此,最后我将获得一个排序的数据结构.