问题标签 [clrs]

是否有可能解决此问题的贪心算法。我已经为它制定了一个 DP 算法，但我不确定它的贪心算法。请解释是否存在贪心算法。

对于那些不熟悉该问题的人：

从 a1 到 a 有“n”个活动。每个活动 ai 都有一个相关的开始时间 si 和一个结束时间 fi 即 [si,fi)。每个活动 ai 也有一个与之关联的值 vi。没有两个活动可以同时发生。任务是选择相互兼容的活动，以使总价值最大化，即所有计划活动的总和。相互兼容意味着它们的运行时间不重叠。

我正在解决一个来自 CLRS 的问题，我们需要证明 (ceil(lg lg n))！是多项式有界的。

现在如果我能证明 theta(lg n)=o(n)

我面临的唯一问题是证明theta(lg n)=o(n)。请帮忙！

在 CLRS 一书中，第 69 页中说 nC2 在单位分而治之（U - 4）中是 Θ(n^2)。谁能解释这个结果是如何正确的？

CLRS 说

我们必须展示关于循环不变量的三件事：

• 初始化：在循环的第一次迭代之前为真。
• 维护：如果在循环的迭代之前为真，则在下一次迭代之前保持为真。
• 终止：当循环终止时，不变量为我们提供了一个有用的属性，有助于证明算法是正确的。

我的问题是我可以编辑这些步骤并改为：

• 初始化：在循环的第一次迭代之后为真。
• 维护：如果循环一次迭代后为真，则在下一次迭代后仍为真。
• 终止：当循环终止时，不变量为我们提供了一个有用的属性，有助于证明算法是正确的。

说明：基本上我们使用数学归纳原理来证明正确性。使用“初始化”，我们证明该属性在第一次迭代后成立。使用“维护”，我们可以证明该属性适用于所有迭代，因为“初始化”和“维护”一起创建了一个链。因此，该属性在最后一次迭代后也成立。

例子：

对于这个算法，教科书中已经有一个使用标准程序给出的证明（因为太长了，我没有在这里包含它）。

我的建议：

• 循环不变量：就在第2-3 行的 for 循环的第 i^次迭代之后，对于每个可能的 (i)-排列，子数组 A[1 .. i] 包含这个 (i)-排列，概率为 (n - i )!/n!。
• 初始化：在第 1^次迭代之后，A[1] 包含这个排列，概率为 (n-1)!/n!=1/n，这是真的。
• 维护：让它在第 (i-1)^次迭代之后为真。在第 (i)^次迭代之后，A[1...i] 包含这个排列的概率为 [(n-i+1)!/n!]*[1/(n-i+1)]=(ni)! /n！这就是我们想要的。
• 终止：在终止时，i = n，我们有子数组 A[1 .. n] 是一个给定的 n 排列，概率为 (n - n)!/n! = 1/n!。因此，RANDOMIZE-IN-PLACE 产生一个统一的随机排列。

我的解释合乎逻辑吗？

任何帮助将不胜感激。谢谢。

所以，最近，出于好奇，我买了 CLRS 的《算法简介》一书。当我开始阅读本书时，我注意到书中一些非常典型的算法以非常不同的方式实现。

给定 CLRS 的快速排序的实现与流行的快速排序 Hoare 算法有很大不同。

所以来回答我的问题...

是 Robert Sedgewick 在他的 Coursera 算法课程中使用的代码。

相比之下，CLRS 中给出的插入排序实现是，

比较奇怪的是运行时间。以下是我运行两种不同实现时的结果：

数组中的元素数：10,000

Robert Sedgewick 的实现耗时：0.235926s

CLRS 实现耗时：0.078608s

有人可以向我解释这些结果吗？该算法几乎相同。只是实现方式不同。实现上的一点点差异怎么会导致运行时间的巨大差异？

根据 CLRS 第 3 版中可用的定义，单连通有向图是这样一种图，其中对于每一对顶点 (u,v)，从 u->v 至多有 1 条唯一路径。现在我读过的大多数答案都表明我们从图中的每个顶点运行 DFS，如果在任何情况下我们找到Cross edge或Forward edge，那么图不是单连接的。我可以理解前向边的概念，但是在这张图上运行这个算法

1 --> 2 <-- 3 会给我们的结果是它不是单连接的，而这个图是单连接的。我们有一个从 3 -> 2 或 1 -> 2 的交叉边，这取决于哪个顶点开始了整个过程（1 或 3）。如果我们从顶点 2 开始 DFS，那么我们有 2 个交叉边 1 -> 2 和 3 -> 2。有人可以澄清一下吗？

我尝试将 CLRS 算法简介中给出的最大子数组问题的伪代码转换为 Python 中的完整工作代码。

代码：

当我尝试运行时，我收到此错误。

错误：

我怎样才能解决这个问题？我哪里出错了？

以下是 CLRS 的算法简介文本。下面是使用有限状态自动机进行字符串匹配的代码片段。Trnstion 函数用于构造带有待搜索模式的状态表。

计算转移函数：以下过程根据给定模式 P [1: :m] 计算转移函数 sigma。

此过程根据方程 (32.4) 中的定义以直接方式计算 sigma(q, a)。从第 2 行和第 3 行开始的嵌套循环考虑所有状态 q 和所有字符 a，第 4-8 行将 sigma(q, a) 设置为最大的 k，使得 Pk 是后缀 Pqa。代码从 k 的最大可能值开始，即 min(m, q+1)。然后它减小 k 直到 Pk 是后缀 Pqa，这最终必须发生，因为 P0 是空字符串，它是每个字符串的后缀。

我对上述代码的问题

1. 为什么作者在第 4 行选择 k 作为 min(m + 1, q+2)？

2. 在下面的解释文本中，作者提到“代码以 k 的最大可能值开始，即 min(m, q+1)。” 哪个与上面第 4 行的伪代码不匹配？

要求在回答上述问题时用简单的例子和​​psudoe代码的步骤来解释。

在第 24 章第 658 页 CLRS 第三版中的 DIJKSTRA 伪代码中，在内部循环中，从新添加的顶点放松相邻边时，为什么允许边上的放松已经从队列中取出并添加到树的最短路径？

为什么内部循环不检查顶点是否已经是最短路径树的一部分，例如，

哪个是正确的方法？

算法的最坏情况时间复杂度与其上限之间的关系/差异是什么？