问题标签 [clrs]

我正在研究 CLRS 并发现了洗牌算法的问题。这会产生均匀随机排列吗？

我的主张：不，它没有。因为，由于第 4 行，将有 n^n 个可能的排列。而且，它不能被 n 整除！这是不同排列的数量。

请您确认我的推理是否正确？

您是否有此解决方案问题的决策树示例。

我想画出决策树用于回答问题（大多数人都能理解）。但我不知道如何绘制这个决策树。举个例子，我不知道叶子是用来表示这个算法的

问题2

假设给你 n 个红色和 n 个蓝色的水壶，它们都有不同的形状和大小。所有红色的水壶都装有不同数量的水，蓝色的也一样。此外，对于每个红色水壶，都有一个装有相同水量的蓝色水壶，反之亦然。

你的任务是找到一组水罐，分成几对装有相同水量的红色和蓝色水罐。为此，您可以执行以下操作：挑选一对红壶和蓝壶，将红壶装满水，然后将水倒入蓝色壶中。此操作将告诉您红色或蓝色水壶是否可以容纳更多的水，或者它们的体积相同。假设这样的比较需要一个时间单位。您的目标是找到一种算法，该算法可以进行最少数量的比较以确定分组。请记住，您不能直接比较两个红壶或两个蓝壶。

1. 描述一种确定性算法，该算法使用 Θ(n2) 比较来将水壶分组成对。2.证明解决此问题的算法必须进行的比较次数的下限 Ω(nlgn)。

为了解决这个问题，算法必须执行一系列比较，直到它有足够的信息来确定匹配。我们可以根据决策树来查看算法的计算。每个内部节点都标有我们比较的两个水壶（一个红色，一个蓝色），并具有三个输出边（红色水壶小于、相同大小或大于蓝色水壶）。叶子上标有独特的水壶匹配。第8 章的解决方案：线性时间排序8-17 决策树的高度等于算法为确定匹配而必须进行的最坏情况比较次数。为了限制这个大小，让我们首先计算 n 个红色和 n 个蓝色罐子的可能匹配数。如果我们在开始比较之前将红色水罐从 1 标记为 n，并将蓝色水罐从 1 标记为 n，该算法的每个结果都可以表示为一个集合 {(i,π(i)) : 1 ≤ i ≤ n 并且 π 是 {1,..., n}} 上的一个排列，其中包含成对的红壶（第一个组件）和匹配的蓝色水壶（第二个组件）。由于每个排列 π 对应于不同的结果，因此必须恰好有 n！不同的结果。现在我们可以限制决策树的高度 h。每棵分支因子为 3 的树（每个内部节点最多有三个子节点）最多有 3h 个叶子。由于决策树必须至少有 n! 孩子们，因此 3h ≥ n! ≥ (n/e) n ⇒ h ≥ n log3 n - n log3 e = (n lg n) 。所以任何解决问题的算法都必须使用 (n lg n) 比较。其中包含配对的红色水壶（第一个组件）和蓝色水壶（第二个组件）。由于每个排列 π 对应于不同的结果，因此必须恰好有 n！不同的结果。现在我们可以限制决策树的高度 h。每棵分支因子为 3 的树（每个内部节点最多有三个子节点）最多有 3h 个叶子。由于决策树必须至少有 n! 孩子们，因此 3h ≥ n! ≥ (n/e) n ⇒ h ≥ n log3 n - n log3 e = (n lg n) 。所以任何解决问题的算法都必须使用 (n lg n) 比较。其中包含配对的红色水壶（第一个组件）和蓝色水壶（第二个组件）。由于每个排列 π 对应于不同的结果，因此必须恰好有 n！不同的结果。现在我们可以限制决策树的高度 h。每棵分支因子为 3 的树（每个内部节点最多有三个子节点）最多有 3h 个叶子。由于决策树必须至少有 n! 孩子们，因此 3h ≥ n! ≥ (n/e) n ⇒ h ≥ n log3 n - n log3 e = (n lg n) 。所以任何解决问题的算法都必须使用 (n lg n) 比较。每棵分支因子为 3 的树（每个内部节点最多有三个子节点）最多有 3h 个叶子。由于决策树必须至少有 n! 孩子们，因此 3h ≥ n! ≥ (n/e) n ⇒ h ≥ n log3 n - n log3 e = (n lg n) 。所以任何解决问题的算法都必须使用 (n lg n) 比较。每棵分支因子为 3 的树（每个内部节点最多有三个子节点）最多有 3h 个叶子。由于决策树必须至少有 n! 孩子们，因此 3h ≥ n! ≥ (n/e) n ⇒ h ≥ n log3 n - n log3 e = (n lg n) 。所以任何解决问题的算法都必须使用 (n lg n) 比较。

这是从 CLRS 获取的用于计算整数分解的伪代码。但是，计算第 8 行中涉及的GCD以及当第 13 行中i == k时需要将 k 加倍有什么意义？请帮忙。

我试图证明 CLRS 练习册中给出的等式。方程是：

我解决了 LHS 但我的答案是 1 而 RHS 应该是 0 以下是我的解决方案：

而所需的 RHS 为 0。我的解决方案有什么问题吗？谢谢..

我正在根据 CLRS 在 C 中实现堆排序算法。但是我无法获得排序的输出。你能看看我的代码有什么问题吗？功能maxheap和buildmaxheap工作。我无法弄清楚代码有什么问题。

该代码应该对数组元素进行堆排序。heapsort()我觉得函数中存在错误，因为maxheapandbuildmaxheap工作得很好。

我得到的最终输出是

但预期的输出应该是

编码：

CLRS 告诉我们交换A[r]其中A[i]i 是 p 和 r 之间的随机变量。但是，如果我要随机选择一个变量作为快速排序函数中的枢轴并交换值，那么现在的时间复杂度是多少？

该算法现在的性能会比书中给出的更差吗？

这是代码

所以问题是：“考虑一个将两个 n 位二进制整数相加的问题，存储在两个 n 元素数组 A 和 B 中。两个整数的和应该以二进制形式存储在 (n+1) 元素中数组 C. 正式陈述问题并编写将两个整数相加的伪代码。”

我解决这个问题的python代码是：

我还取了左边的最低有效数字，在我完成计算后我可以反转。

我无法弄清楚错误是什么，请帮忙！

在以下 MIT 讲座中： https ://www.youtube.com/watch?v= JZHBa-rLrBA 在 1:07:00，教授教计算不成功搜索中的探针数。

但我的计算方法与他不符。我的回答是：

探针数=

m=没有。哈希表中的槽数

n = 没有。元素（键）

解释：

1.哈希函数可以命中一个空槽，概率为mn/m。

2.或者它可以以 n/m 的概率命中一个被占用的键槽。

3.现在在情况 2 中，我们将不得不再次调用哈希函数，有两种机会： (i) 我们得到一个没有密钥的槽，概率为 (mn)/(m-1)。(ii) 我们得到一个带有概率 (n-1)/(m-1) 的密钥槽。

4.现在重复案例 3，但概率不同，如图所示

为什么我得到不同的答案。它出什么问题了？

我正在从 CLRS 学习字符串匹配与有限自动机。我正在解决一些练习题。对于练习题 32.3-1，

为模式 P = aabab 构造字符串匹配自动机，并说明它对文本字符串 T = aaababaabaababaab 的操作。

以下是我的过渡功能，

我的转换功能正确吗？我如何填写最后一行？任何帮助

对于分段树的惰性传播算法，我有一些不清楚的地方。根据下面的代码，当查询间隔完全重叠时，更新值只是添加到父节点，子节点被标记为延迟更新。但正如您在所附图片中看到的那样，如果对范围 0,1 进行了 +4 更新，那么两棵树的结果完全不同！（左图：没有延迟传播）。

所以问题是，如果在 +4 更新后调用了一个询问 0,1 和的查询怎么办？