问题标签 [clrs]

CLRS 练习：6.5-8

该操作从堆中HEAP-DELETE(A,i)删除节点中的项目。给出一个针对 n 元素最大堆及时运行的实现。iAHEAP-DELETEO(lg n)

我想知道算法对于输入A[10]={84,22,19,21,3,10,6,5,20}（索引从 1 开始）和A[6]=10被删除是否错误。替换最后一个节点A[6]会导致违反堆属性，忽略父值。

我为此编写了一个算法，想知道它是否工作正常或我哪里出错了？

算法介绍CLRS 4.3 (b) 有问题

T(n) = 3*T(n/3) + n/lg(n)

注意 n^(log a/ log b) = n^(log 3/ log 3) = 1

该书指出，这里不能应用主定理情况 3，因为 n/log (n) 不是多项式更大的，即它渐近小于 n^(k)，其中 k 是任何正常数。

我的问题是：假设 k = 0.1 那么 n/log (n) 总是渐近大于 n^(0.1)，但这与上述说法相矛盾。我究竟做错了什么？

我试图实现最大子数组问题的Brute方法（clrs 4.1-2），我认为我（很容易）得到它：
PSEUDO-CODE：

但是当它只返回一个元素时问题就来了(from = to)，因此，我们应该考虑一个案例 when from = to，但这要么排除了有用的案例，要么包含了多余的案例。

示例：
如果输入是 1,-4,3,-4 那么它会返回一个错误的答案（就像只有 3 是第 3 个元素）。
任何帮助表示赞赏。
月亮

编辑：1）天数更改为 A.length
2）我想知道我们如何处理当 时的情况from = to，也有最大值sum。
3)0改为sum在伪代码的第 5 行。

在 DFS 和 BFS 的实现中，CLRS 作者为每个顶点区分了 3 种颜色——灰色、黑色和白色。我知道黑白表示节点是否被访问。为什么我们需要灰色？

我的猜测是检测周期，但我们也可以检测只有黑白（即没有灰色）的周期吗？

鉴于 CLRS 算法书中的以下问题。

对于下表中的每个函数 f(n) 和时间 t，确定在时间 t 可以解决的问题的最大大小 n，假设解决问题的算法需要 f(n) 微秒。

1. 当时间为 1 秒时，如何计算 f(n)=nlog(n) 的 n？
2. 对于 f(n)=n，如何计算 n！什么时候是1秒？

考虑这个问题：- 从链式哈希表中有效地挑选一个随机元素？

并认为这是第一个答案。它提出了一种以均匀随机方式选择密钥的方法。然而，这对我来说还不清楚。第一步将采用概率1/m（即从 m 个桶中随机选择一个桶）
，而第二步可以分为两个步骤：
1）如果k<=p，则返回 p。
2）如果k>p然后循环再次运行。
这样做直到返回 p。
所以一个键被选中的概率是：
(1/m)[(k1/L)+((L-k1)/L)[(1/m)[(k2/L)+((L-k2)/L)[(1/m)[(k3/L)+((L-k3)/L)[......and so on.
现在这怎么能等于1/n？

我读了几篇文章说，在堆中，只能删除根元素。但是，为什么我们不能使用以下方法删除元素？

1. 找到要删除的关键元素的索引
2. 把这个元素和最后一个元素交换，这样key就变成了最后一个元素
3. 从键的原始索引开始重新堆化（您现在已与最后一个元素交换）
4. 将堆大小减少 1

所以，代码看起来像

在最坏的情况下，R-select 是 O(n^2)，而 select 是 O(n)。有人可以解释和对比他们在一般情况下的行为吗？

Ps - 我不确定它是否是一个重复的问题。如果是这样我可以删除！谢谢！！

考虑对于二叉搜索树，我们有 n 个相同输入的情况。我们从x.left和x.right中随机选择，同时插入节点。

clrs (12-1-(d)) 中有一个问题，要求我们推导出此设置的预期运行时间。直观地说，答案就是 O(n lg n)。但是我怎么证明呢？

任何建议表示赞赏。

月亮。

我正在尝试从 clrs book 实现队列，但它没有按预期工作。我的代码有什么问题？

这可能是队列大小或入队操作的问题吗？

但是，很明显队列上的入队操作没有按预期工作。这是我的代码：