我已经想出了如何从下面的问题中得到2n/3：
‘子树的每个子树的大小都不超过2n/3-最坏的情况发生在树的底部恰好是半满的时候“T(n) &
浏览 13提问于2017-12-16得票数 0
在CLRS，第三版，第155页上，给出了在MAX-HEAPIFY中，我的问题是如何得到2n&#
浏览 84提问于2012-02-02得票数 86
回答已采纳
在，第三版，155页上，给出了在MAX-HEAPIFY中，我猜原因是在这种情况下，Max-Heapify必须通过左子树“向下浮动”。但我不明白的是“为什么是半满的”？
如果左子树只有一个叶子，Max-Heapify也可以向下浮动。那么为什么</em
浏览 2提问于2011-07-28得票数 16
回答已采纳
在第155页的CLRS中，最大堆的运行时间被描述为T(n) = T(2n/3) + O(1).我理解为什么第一次递归调用是针对一个大小为2n/3的子问题，在这样的情况下，我们有一个几乎完全的二叉树(总是堆的情况)，其中最深的节点层是半满的(我们递归到子树的根上，它是包含这些
浏览 2提问于2016-07-29得票数 3
回答已采纳
1回答
问题2-1:(A)显示插入排序可以在O(nk)最坏情况下对长度为k的n/k子列表进行排序。答案是：
Ans:在最坏的情况下，插入排序每个k元素列表需要(
浏览 0提问于2013-08-23得票数 0
回答已采纳
1回答
从算法推导时间复杂度
、、、、
在我的课堂笔记中，提供了一个选择排序算法(如下面的代码所示)。注释提出了以下问题：“导出一个函数f(n)，它对应于在最坏情况下修改 minIndex或nums 的所有位置的总次数。现在，注释告诉我，答案是f(n)= 1/2n^2 + 5/2n + 3。我想知道是否有人能解释这种情况是如何发生的。”
我的教授让我们数一数内环的操作，然后找出我们<
浏览 2提问于2017-09-24得票数 0
2回答
我搞不懂堆的事。
我无法理解这一点。为什么半满？..为什么？我认为如果有更多的树，可能需要更多的时间。否则就少花点时间。
感谢您的阅读
浏览 2提问于2015-04-19得票数 2
回答已采纳
我们如何判断一个算法的获得时间复杂度是最好的，还是最坏的，还是平均的？例如，如果我们得到时间复杂度为t(n) = 2n^2 + 3n -1，如何估计最好或最坏或平均的情况？
浏览 0提问于2011-09-16得票数 2
1回答
我需要找到最有效的算法合并2个最大堆。
一些重要的事实:堆被表示为一个二叉树，这意味着每个节点都有三个字段--值(键)、指向右子节点的指针和指向左子节点的指针。我的想法是:取第二堆的最后一页，把他作为新堆的根。所以我们得到一个新的堆，当左子是一个合法的最大堆，而右边的子堆是一个合法的最大堆。问题(在我看来)只是根不是最大元素的事实，所以我们可以从
浏览 1提问于2015-12-12得票数 2
回答已采纳
3回答
让我困惑的是选择5个元素的块而不是3个元素的块。在我看来，对于5个元素的块，您执行的是n/4 = n/5 + n/25 + n/125 + n/625 + ... 5中值运算，而对于3个元素的块，您执行的是n/2 = n/3 + n/9 + n/27+ n/81 + ... 3<em
浏览 0提问于2010-10-12得票数 11
回答已采纳
1回答
假设线性选择使用大小为3的子序列，最坏情况下的运行时间不再是O(n)。我得出的结论是时间复杂度是3n+T(n/3)+T(2n/3)。现在假设T(n)等于或小于cn。但是当我分离c的时候，我不能得到c，它们只是相互抵消。发生这种情况是因为它不是cn吗？
浏览 14提问于2020-05-24得票数 1
回答已采纳
我理解为什么在最坏的情况下，T是该算法的运行时间，而使用具有大小为3的块的中间值算法会给出一个递归关系。T(n) = T(2n / 3) + T(n / 3) + O(n)
表示，对于大小为3的块，运行时不是O(n)，因为它仍然需要检查所有n个元素。我不太明白这个解释，在我的家庭作业中，它说我需要通过归
浏览 1提问于2016-06-06得票数 1
2回答
尝试理解max heapify
、、、、
我不理解max-heapify的功能。它看起来像一个递归函数，但不知何故，由于树的高度，它被认为是以对数时间运行的。
对我来说，这毫无意义。在最坏的情况下，它不是必须颠倒每一个节点吗？我不明白如何在不重复触及每个节点的情况下做到这一点。
浏览 0提问于2016-01-28得票数 5
回答已采纳
1回答
我们知道，找到列表中最小数字的最简单方法是简单地进行n次比较，如果我们想要第二个最小的数字，我们可以再次检查它，或者在第一次迭代期间跟踪另一个变量。无论哪种方式，这将需要2n次比较才能找到这两个数字。但是假设你不得不使用简单的算法，这个算法需要2n次比较。在最坏</e
浏览 4提问于2013-03-11得票数 1
回答已采纳
,a_n}
在数组中找到两个元素之间的最大差异(在最坏的情况下使用至多3/2n比较的max|a_i-a_j|))(运行时无关紧要，我们不能使用诸如max或min之类的操作)。我真的很怀疑这是否可能:为了找到两个元素的最大差异，在最坏的情况下，我们不应该总是需要关于2n比较，因为我们需要使用大约n个比较来找到数组中最大的元素，并使用另外n
浏览 0提问于2021-02-17得票数 4
1回答
3递推T(n)与主定理
、、、、
假设我有下面的代码，我的任务是查找递归的T(n)及其最坏的运行时。如果n是列表的长度的值。在这种情况下，我们有3个递归，mystery(mylist[:len(mylist)-t-1])、mystery(mylist[t:len(mylist)- 1])和mystery(mylist[:len(mylist[:len(mylist)-t-1])
对于递归情况，我的观察是因为递归是在一起的，所以递归是
浏览 6提问于2021-11-08得票数 1
1回答
在通过时，我发现了max-heapify算法的递归关系.事实上，我的老师很小地证明，最大化过程的时间复杂性是O(logn)，这仅仅是因为最糟糕的情况是，根必须从顶部一直到最后一层“泡沫/漂浮”。这意味着我们逐层移动，因此步骤的数量等于堆的级别/高度的数目，正如我们所知，堆的高度是由logn所限制的。当然可以。
然而，同样的情况
浏览 5提问于2021-05-22得票数 1
回答已采纳
1回答
在这个中，作者说get(index)在ArrayList中是O(1)，而在LinkedList中是O(n/2)，因为它需要遍历直到那个条目。在ArrayList中使用恒定时间的get操作是有意义的，因为ArrayList可以访问所有索引。但是，我不理解LinkedList的O(n/2)。我被教导的方式是，当你使用大的哦符号，你应该写它没有常数，使它更容易解释给别人；也就是说，O(n)，而不是O(2n</em
浏览 3提问于2014-09-18得票数 1
回答已采纳
很难找到最坏情况下的时间复杂度。本例适用于大小相同(n)的两个排序数组的交叉。不确定如何计数带两个条件的while循环，也不确定如何计数if和else if语句
我知道最大的0将是N+N，但不知道如何显示最坏的情况。
浏览 3提问于2020-11-20得票数 0
回答已采纳
云服务器
对象存储
ICP备案
云点播
实时音视频
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号