在CLRS，第三版，第155页上，给出了在MAX-HEAPIFY中，我的问题是如何得到2n&#
浏览 84提问于2012-02-02得票数 86
回答已采纳
我已经想出了如何从下面的问题中得到2n/3：
‘子树的每个子树的大小都不超过2n/3-最坏的情况发生在树的底部恰好是半满的时候“
然而，我想知道，当树的底部恰好是半满的时候，我们得到</em
浏览 13提问于2017-12-16得票数 0
我们如何判断一个算法的获得时间复杂度是最好的，还是最坏的，还是平均的？例如，如果我们得到时间复杂度为t(n) = 2n^2 + 3n -1，如何估计最好或最坏或平均的情况？
浏览 0提问于2011-09-16得票数 2
1回答
从算法推导时间复杂度
、、、、
在我的课堂笔记中，提供了一个选择排序算法(如下面的代码所示)。注释提出了以下问题：“导出一个函数f(n)，它对应于在最坏情况下修改 minIndex或nums 的所有位置的总次数。现在，注释告诉我，答案是f(n)= 1/2n^2 + 5/2n + 3。我想知道是否有人能解释这种情况是如何发生的。”
我的教授让我们数一数内环的操
浏览 2提问于2017-09-24得票数 0
1回答
问题2-1:(A)显示插入排序可以在O(nk)最坏情况下对长度为k的n/k子列表进行排序。答案是：
Ans:在最坏的情况下，插入排序每个k元素列表需要(k^2)时间。因此
浏览 0提问于2013-08-23得票数 0
回答已采纳
在第155页的CLRS中，最大堆的运行时间被描述为T(n) = T(2n/3) + O(1).我理解为什么第一次递归调用是针对一个大小为2n/3的子问题，在这样的情况下，我们有一个几乎完全的二叉树(总是堆的情况)，其中最深的节点层是半满的(我们递归到子树的根上，它是包含这些节点的</
浏览 2提问于2016-07-29得票数 3
回答已采纳
3回答
我正在开发一个基于的快速排序变体实现，用于选择一个好的pivot元素。传统的智慧似乎是将数组分成5个元素的块，取每个元素的中位数，然后递归地将相同的分块方法应用于产生的中位数，以获得“中位数”。让我困惑的是选择5个元素的块而不是3个元素的块。在我看来，对于5个元素的块，您执行的是n/4 = n/5 + n/25 + n/12
浏览 0提问于2010-10-12得票数 11
回答已采纳
1回答
我需要找到最有效的算法合并2个最大堆。
一些重要的事实:堆被表示为一个二叉树，这意味着每个节点都有三个字段--值(键)、指向右子节点的指针和指向左子节点的指针。我的想法是:取第二堆的最后一页，把他作为新堆的根。所以我们得到一个新的堆，当左子是一个合法的最大堆，而右边的子堆是一个合法的最大堆。问题(在我看来)只是根不是最大元素的事实，所以我们可以从根运行函数
浏览 1提问于2015-12-12得票数 2
回答已采纳
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回答
假设线性选择使用大小为3的子序列，最坏情况下的运行时间不再是O(n)。我得出的结论是时间复杂度是3n+T(n/3)+T(2n/3)。现在假设T(n)等于或小于cn。但是当我分离c的时候，我不能得到c，它们只是相互抵消。发生这种情况是因为它不是cn吗？
浏览 14提问于2020-05-24得票数 1
回答已采纳
我正在处理一个带有整数元素的未排序数组，在数组中找到两个元素之间的最大差异(在最坏的情况下使用至多3/2n比较的max|a_i-a_j|))(运行时无关紧要，我们不能使用诸如max或min之类的操作)。我真的很怀疑这是否可能:为了找到两个元素的最大差异，在最坏的情况下，我们不应该总是需要关于2n
浏览 0提问于2021-02-17得票数 4
1回答
无论哪种方式，这将需要2n次比较才能找到这两个数字。但是假设你不得不使用简单的算法，这个算法需要2n次比较。在最坏的情况下，需要2n次比较。但是平均数是多少呢？使用简单的蛮力算法找到最小的和第二小的平均比
浏览 4提问于2013-03-11得票数 1
回答已采纳
我理解为什么在最坏的情况下，T是该算法的运行时间，而使用具有大小为3的块的中间值算法会给出一个递归关系。T(n) = T(2n / 3) + T(n / 3) + O(n)
在这
浏览 1提问于2016-06-06得票数 1
1回答
仅通过查看算法，似乎很明显其复杂性将在(log (n - m))范围内，因为每次递归调用时实例大小除以3。A[n] = temp if (m + 1 < n) then WeirdSort(A[m..n - index]) end if但我正在尝试理解如何通过向后替换的</e
浏览 7提问于2017-02-16得票数 0
很难找到最坏情况下的时间复杂度。本例适用于大小相同(n)的两个排序数组的交叉。不确定如何计数带两个条件的while循环，也不确定如何计数if和else if语句
我知道最大的0将是N+N，但不知道如何显示最坏的情况。
浏览 3提问于2020-11-20得票数 0
回答已采纳
如果我有一个大小为n的列表，并且我知道列表中的数字将介于1到2n之间，我将如何解决最坏情况是O(n)的问题呢？我在想，如果它介于1和n之间，我只需要取这个数字，并将它与数组的值交换-1，但是如果有任何重复的话，它就不会排序。
我在考虑一种类似的方法，对于数字介于1到2n之间的列表，但我似乎无法弄清楚。
浏览 6提问于2013-12-01得票数 5
回答已采纳
2回答
一类递归和无递归算法的时间复杂度
、、、、
multiplyVec[1]; multiplyVec[1] × multiplyVec[n] + AnotherRecursiveAlgo(multiplyVec[2n/3 to n]);
我需要分析这些算法的时间复杂度:对于我得到的第一个算法，第一个循环在O(n)中，第二个循环有一个最好的情况</em
浏览 8提问于2016-10-20得票数 0
回答已采纳
2回答
我从字面上和实际意义上理解它，通过这样的类似问题的答案。但答案不能解释，我不明白的是它背后的数学基础。在某种程度上，我直觉地了解到，这个方程试图用某种意义上斜率较高的函数来计算上界，而在函数f(n)的较高一端。我知道我的理解很模糊。因此，请有人解释一下大O表示法的数学基础/表示。
浏览 6提问于2014-05-13得票数 1
回答已采纳
作为Ө(n^2)的插入排序的运行时间意味着它具有上界O(n^2)和下界Ω(n^2)。我很困惑插入排序下界是Ω(n^2)还是Ω(n)。
浏览 0提问于2013-03-25得票数 1
回答已采纳
我知道，长度N的长度编码文本在最坏情况下的空间使用量与N (2N?)成正比。所以O(N)
我还知道，对于某一列的位图索引数量，最坏的情况是当该列的基数为N时，其中N是表中的记录数(因此每个记录在该特定列中都有一个唯一值)。这意味着将有N个位图索引。然而，在位图索引的最坏情况下，每个位图索引，当运行长度编码时，将有固定的<
浏览 2提问于2014-12-16得票数 2
回答已采纳
云服务器
ICP备案
对象存储
云点播
实时音视频
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号