algorithm – 搜索最大堆中的第7个最大元素？
发布时间：2020-12-15 05:02:44 所属栏目：Java 来源：网络整理
导读：所以我和我的朋友在这个问题上没有一致的看法.它要求在n个元素的最大堆中搜索第7个最大元素的时间复杂度？ 我认为它应该是O(n)并且她认为它应该是O(1).我的逻辑是假设n是7然后第7个最大元素将是堆中的最后一个元素,所以如果我们考虑最坏的情况它应该是O(n).
|
所以我和我的朋友在这个问题上没有一致的看法.它要求在n个元素的最大堆中搜索第7个最大元素的时间复杂度？
我认为它应该是O(n)并且她认为它应该是O(1).我的逻辑是假设n是7然后第7个最大元素将是堆中的最后一个元素,所以如果我们考虑最坏的情况它应该是O(n).然而她说,因为它是最大堆,所以找到第7大元素应该花费不变的时间.但是使用她的逻辑甚至可以在O(1)时间内找到第50大元素或第100大元素. 有人可以告诉我哪种解决方案是正确的？ 解决方法
有一个O(1)解决方案.我们假设堆被重新树作为树,而max元素是根.比具有第7个最大元素的节点与根之间的距离小于或等于6.距离根<= 6的节点的数量永远不会大于1 2 4 8 16 32 64 = 127.这是一个常数.它们可以在恒定的时间内穿越.
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |