问题标签 [clrs]

我在 MATLAB 中编写了一个堆排序函数，它工作正常，只是当输入的长度大于或等于 1000 时，它可能需要很长时间（例如 1000 的长度需要半秒）。我不确定是 MATLAB 在堆排序算法上运行得不是很快，还是只是我的代码需要改进。我的代码如下所示：

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

我知道可能是代码a(n+1-i) = [];可能会消耗大量时间。但是当我将 in 更改[]为-999（低于输入向量的任何数量）时，它无济于事，反而花费了更多时间。

我正在关注 CLRS 书，并在我继续使用 python 中实现所有算法，这是合并排序算法。我在一个测试数组上测试了 merge 函数，它可以工作，所以它必须是 merge_sort 函数，但是它与书中的伪代码几乎相同。

我通常看到两个版本的 Master 定理。

版本 1：

（来自Tim Roughgarden 的课程）

对于形式的递归关系，

有3个案例，

版本 2：

（来自CLRS）

对于形式的递归关系，

有3种情况：

问题： 应该支持哪个版本，为什么？

这是数组中线性搜索的伪代码，如果找到数组中i的所需元素，则返回索引，否则（来自 CLRS 书，第 3 版，练习 2.1-3）：eANIL

我试图从中推断出一个不变量的循环，所以根据我的理解，我认为一个由以下事实表示，即在循环中的任何给定时刻子数组A[1..i-1]仅包含相等性测试证明为假的值。

具体来说，在第一次迭代之前，i-1 == 0这意味着子数组的长度为空，因此不能存在v属于它的元素，使得v == e. 在任何下一次迭代之前，作为等式测试也是退出条件，假定的不变属性必须仍然成立，否则循环将已经结束。在终止时，要么是函数即将返回一个索引（在这种情况下，循环不变量是平凡的），要么是返回 NIL（在这种情况下i == A.length + 1，所以循环不变量对任何1 < j < i）。

以上是正确的吗？如果不是，您能否提供一个正确的循环不变量？

感谢您的关注。

我是一名自学成才的计算机科学专业的学生。现在我正在阅读 CLRS 并且我做了 2.2-2 练习，它是关于选择排序的。

第一个数组下标为 1。

我写的伪代码是：

我的理由是：
第一个循环测试执行 n 次 (1, 2, 3 ... n)。当 i 变为 n 时，循环停止。所以第 5 行被执行 (n-1) 次，依此类推。

然后我认为第二个循环测试执行了 (n^2 + n - 2)/2 次。当初始 j = 2 时，假设：2、3、4、5 ... (n + 1)，循环测试执行 n 次，当 j = 3 时，循环测试执行 (n - 1) 次，依此类推上。因此，当 j = n 时，循环测试执行 2 次。

因此，执行第二个循环测试： 2 + 3 + 4 + 5 + ... + n = [(n-1)*(n+2)] / 2 = (n^2 + n - 2) / 2.所以执行第二个循环的内部if：1 + 2 + 3 + 4 + ... + (n-1) = [(n-1)*n] / 2。

在写这篇文章之前，我读了很多假设的解决方案，但没有一个能和我的一样。所以我想知道我的推理是否错误。

我希望我以良好的形式写下了所有细节。

我正在尝试解决这个问题（CLRS，第 3 版，练习 11.2-1）：

假设我们使用散列函数 h 将 n 个不同的键散列到长度为 m 的数组中。假设简单的统一散列，预期的冲突数量是多少？

正确的解是n(n-1)/2m。这取自 CLRS 的讲师手册。

我的解决方案如下：

• 对于键 1 的插入：预期与前任的冲突数 = 0

• 对于键 2 的插入：预期与前任的冲突数 = 1/m

• 对于键 3 的插入：预期与前任的冲突数 = 1/m*(1/m) + (m-1)/m*(2/m) = (2m-1)/m^2

我的推理：密钥 1 和 2 在 1 个插槽中发生碰撞的概率为 1/m，这意味着密钥 3 的碰撞概率为 1/m。密钥 1 和密钥 2 没有冲突的概率为 (m-1)/m，这意味着它们位于不同的插槽中，密钥 3 的冲突概率为 2/m。

3 个键的预期碰撞次数，由期望的线性度 = 0 + 1/m + (2m-1)/m^2 = (3m-1)/m^2

根据 CLRS，3 个键的预期碰撞次数应该是 3/m。

我知道如何使用指标 RV's 找到正确的解决方案。

我的问题是：我的解决方案哪里出错了？为什么不一样？

考虑 CLRS 书中完整 k-ary 树的以下定义：

定义：一棵完整的k-ary树是一棵k -ary树，其中所有叶子都具有相同的深度，并且所有内部节点的度数为k。（第 1179 页）

由于这个定义，我认为下一个二叉树是完整的

CLRS 完成二叉树

但是基于这个完整树的答案定义（完整二叉树，k叉树的特例），

一棵二叉树，其中每一层，除了可能是最深的，都被完全填满。在深度n处，即树的高度，所有节点都必须尽可能靠左。

这与 Grimaldi 的离散数学书（第 601 页）中出现的相同，我们认为下面的有根树是一棵完整的树

完成的二叉树

但这对于 CLRS 定义是不正确的，因为G离开它与其他定义不同。这两个定义中哪一个是最常用和最适合该案例的？

I have read the definition of big O in the introduction to algorithm which book doesn't talk about my confusion.

According to its definition, everybody knows the function T(n) = 3n belongs to O(n),my confusion is whether all functions what belongs to O(n) belongs to O(n^2) and O(n^3) and O(n^4) and O(n^k) k>1, because the big O describes the upper limit,and I aways can find the positive integer constant c and positive integer constant n0 to meet 0<=3n<=cn^2 when n>=n0, if the answer is YES, why do people prefer th use O(n) to describe T(n) = 3n if its definition is serious?

More, where are these notations(big O, big theta, big omega) been used in other math field?

Please post the necessary references or any other books which talk about this

谁能告诉我这个问题的算法？Q..我们可以将插入排序表示为递归过程，如下所示。为了对 A[1..n] 进行排序，我们递归地对 A[1..n-1] 进行排序，然后将 A[n] 插入到排序后的数组 A[1..n-1] 中。为这个递归版本的插入排序的运行时间写一个递归。

我知道该算法使用时间复杂度的 8 次乘法和 4 次加法：

乘法是在每个n/2 * n/2矩阵上完成的。我对此有几个问题：

1. 每个n * n矩阵是否最终通过执行减小到n=1大小T(n/2)？如果这样返回a11*b11似乎没有意义，就像1*6为a11*b11下面的矩阵返回：

然后基本情况应该n==2执行 else 部分，因为下面的操作似乎是合法的。

2. 为什么要加法部分0(n^2)？我的意思是，我们完全不处理矩阵加法，而只是处理数字，因为每个矩阵都简化为2 * 2如下所示：

所以加法部分应该只贡献4？（为什么0(n^2)？）