问题标签 [clrs]

在 CLRS（Cormen、Leiserson、Rivest 和 Stein的算法简介）中，对于一个函数

f ( n ) =一个² + bn + c

他们说

假设我们采用常数c ₁ = a /4、c ₂ = 7 a /4 和n ₀ = 2·max(| b |/ a , √(| c |/ a ))。
那么 0 ≤ c ₁ n ² ≤ an ² + bn + c ≤ c ₂ n ²对于所有n ≥ n ₀。
因此f ( n ) 是 Θ( n ² )。

但是他们没有具体说明这些常量的值是如何来的？
我试图证明它，但不能。
请告诉我这些常数是怎么来的？

在CLRS，第三版，第 155 页，给出了在 MAX-HEAPIFY 中，

我猜原因是在这种情况下，Max-Heapify 必须通过左子树“向下浮动”。
但我无法得到的是“为什么半满”？
如果左子树只有一个叶子，Max-Heapify 也可以向下浮动。那么为什么不认为这是最坏的情况呢？

在 CLRS 的 Introduction to Algorithms 3rd edition P.525 中，在分析 size(x) 的下界时，我引用了一句话“因为向节点添加子节点不能减小节点的大小，所以 Sk 的值增加与 k 单调”。但实际上，我想我可以举一个反例来说明 Sk 不一定随 k 单调递增。在下图中，key=1的节点度数为2，没有其他度数为2的节点，所以S2=8。同样，S3=6。但现在 S3 小于 S2，这意味着 Sk 根本不随 k 单调增加。

堆可以通过执行一系列切割和级联切割从无序二项式子树派生。

我想知道上述结构是否是有效的斐波那契堆。如果是这样，那么它也是一个有效的反例。

嗨，我正在阅读关于 CLRS 上的通用散列的章节。

在第 234 页

推论 11.4

通过在具有 m 个槽的表中链接使用通用散列和冲突解决方案，需要预期时间 Theta(n) 来处理包含 O(m) 个 INSERT 操作的 n 个 INSERT、SEARCH 和 DELETE 操作序列。

我有点明白这个想法，但我很难理解这个英文句子。结尾“包含 O (m) INSERT 操作”是什么意思？

这是否意味着已经执行了 n = O(m) 插入。然后，....我不知道。我无法解析这句话。第一次插入和第二次插入有什么区别？

我想听听你的意见。

谢谢！

CLRS 第 3 版“最坏情况线性时间的选择”中的第 9.3 节讨论了“选择”算法（由于 Blum、Floyd、Pratt、Rivest 和 Tarjan，有时称为 BFPRT 算法）用于在 O 中查找列表的中值(n) 最坏情况下的时间。当我试图在白板上运行示例时，我有点困惑。我知道每次调用“Select”时可以消除一定数量的元素（我读过 30% 被消除，而 70% 需要再次检查），我感到困惑的是数组的哪一部分可以是消除，即如果数组被可视化为高度为 5 和宽度为 n/5 的矩阵，那么消除的元素位于哪个象限？我最初认为它是两个对角相邻的象限，但现在我认为它只是一个象限，具体取决于中位数的中位数是多少（参见步骤 5、6 和 7在这里）。

所以我去维基百科看看是否有一个比CLRS分析更少的快速解释（为了在我跳回CLRS进行分析之前理解算法）。我想到了这一点，特别是“最后，选择“中位数的中位数”作为支点。” 从维基百科中描述的声音来看，“选择”没有找到真正的中位数，而是一个足够中位数的元素，用于选择快速排序的枢轴。

那么“选择”在真正的中位数方面做了什么，它是如何做到的？通过所有这些想到的短语是“部分层次结构”，据我所知，这就是“选择”起作用的原因，但是根据这个部分层次结构，你可以通过什么逻辑从列表中删除元素而不是中间值？

我很难理解来自 CLRS 的以下引理：

_{设 G 是一个流网络，s 和 t 是源和汇节点，f 是从 s 到 t 的预流，h 是 G 上的高度函数。那么在残差图 G f}中没有从 s 到 t 的增广路径.

为什么是这样？

最近，我正在尝试解决 CLRS 中的所有练习。但有一些我无法弄清楚。这是其中之一，来自 CLRS 练习 12.4-2：

描述在 n 个节点上的二叉搜索树，使得树中节点的平均深度为 Θ(lg n)，但树的高度为 ω(lg n)。给出一个 n 节点二叉搜索树高度的渐近上限，其中节点的平均深度为 Θ(lg n)。

任何人都可以分享一些想法或参考来解决这个问题吗？谢谢。

从关于 Hashtable 类的 Java 文档中，它说

作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷

所以 Hashtable 的加载因子是 0.75，这意味着如果有 N 个键，Hashtable 将使用 M = N/0.75 个空格来存储它们。

在 CLRS 书中，它还介绍了负载因子 alpha。

但据我了解，CLRS 打算将 alpha 设置为大于 1，即 M = N/alpha < N。这意味着 Hashtable 可以使用 M 个插槽，其中 M < N 以便它可以节省未使用键的存储空间。

我说 M < N 可以节省存储空间，因为通常我们不知道 N 的确切值，但我们知道键的集合并使用 N 代表可能的键数。密钥的集合可能非常大，但实际使用的密钥数量非常少。所以设置 M 小于 N 可以节省存储空间。这也是为什么通常 Hashtable 不使用直接数组来映射每个 {key, value} 1:1 的原因。

但是 Java 中的 Hashtable 使用存储多于 N。我认为这与 CLRS 设计不相符，对吧？

我对吗？

谢谢

我正在自学 CLRS 第 3 版，这是我遇到的更棘手的问题之一，以及它作为对所有人的服务的答案。

7.4-5 我们可以在实践中利用插入排序在输入“接近”排序时的快速运行时间来提高快速排序的运行时间。在元素少于k元素的子数组上调用快速排序时，让它简单地返回而不对子数组进行排序。在对快速排序的顶级调用返回后，对整个数组运行插入排序以完成排序过程。认为这种排序算法在O(nk+nlg(n/k))预期时间内运行。我们应该如何选择k，无论是在理论上还是在实践中？

是的，这将是一个家庭作业（我是自学而不是大学）问题，但我不是在寻求解决方案。相反，我希望澄清问题本身。

在CLRS 第 3 版，第 593 页，消费税 22.1-5，

有向图 G = (V, E) 的平方是图 G ² = (V, E ² )使得 (u,v) ∈ E ²当且仅当 G 包含一条在 u 之间最多有两条边的路径和 v。描述为 G的邻接列表和邻接矩阵表示从 G计算 G ^{2的有效算法。分析算法的运行时间。}

然而，在 CLRS 第 2 版中（我再也找不到书的链接），第 530 页，同样的练习，但描述略有不同：

有向图 G = (V, E) 的平方是图 G ² = (V, E ² ) 使得 (u,w) ∈ E ²当且仅当对于某些 v ∈ V，两者 (u,v ) ∈ E 和 (v,w) ∈ E。也就是说，只要 G 包含一条在 u 和 w 之间恰好有两条边的路径，G 2 就在 u 和 w 之间包含一条^边。描述为 G的邻接列表和邻接矩阵表示从 G计算 G ^{2的有效算法。分析算法的运行时间。}

对于“正好两条边”的老练习，我能理解也能解决。例如，对于邻接列表，我只需执行 v->neighbour->neighbour.neighbour，然后将 (v, neighbour.neighbour) 添加到新的 E ²中。

但是对于“最多两个边缘”的新练习，我很困惑。

“当且仅当 G 包含一条在 u 和 v 之间最多有两条边的路径”是什么意思？

由于一条边可以满足“最多两条边”的条件，如果 u 和 v 只有一条包含一条边的路径，我应该将 (u, v) 添加到 E ²吗？

如果 u 和 v 有一条有 2 条边的路径，但也有另一条有 3 条边的路径，我可以将 (u, v) 添加到 E ²吗？