clrs_编程技术问答社区_程序员问答知识库

以下是关于 clrs 的编程技术问答

Mergesort导致CLR中的错误(第三版)

根据 def merge(a, p, q, r): n1 = q - p + 1 n2 = r - q left, right = [], [] for i in range(1, n1): left.append(a[p + i - 1]) for j in range(1, n2): right.append(a[q + j]) left.append(float('inf')) right.append(float('inf')) i, j = 1, 1 for k in range(p, r): if left[i]

12 2023-03-26 编程技术问答社区 python mergesort clrs

CLRS解决方案似乎毫无意义，因为一行使我怀疑

问题:表明，随机选择永远不会递归调用0长度的数组. 提示:不要假设输入数组是空的，即p> r.相反，表明如果一个空 (sub-)数组曾经通过随机分区生成，那么递归调用将不会在如此空的(子)阵列上制作这是科尔森算法介绍的练习问题.第9章.中位数和订单统计练习号9.2-1. 答案应该是: 调用0长度数组将意味着第二个和第三个参数相等.因此，如果在第8行上进行呼叫，我们需要p = q -1，这意味着q -p + 1 = 0. 但是，我被认为是一个非负号，要执行第8行，我们需要i k = q -p + 1 = r -p.这将是对数组的毫无意义的原始调用可以找到此解决方案算法可以找到Cormen的算法简介第9章.中位数和秩序统计第9.2节预期线性时间中的选择行号8:算法说return RANDOMIZED-SELECT(A,p,q-1,i) 解决方案说第二个和第三个参数应该相等，因此，p=q-1表示p-q+1 =0，但在解决方案中给出了q - p +

6 2023-03-24 编程技术问答社区 algorithm median clrs

在quickSort中，什么是预期值（数学），它背后的原因是什么？

我需要帮助解释公式我的问题在页面屏幕截图中叠加. 此公式是关于Qiucksort算法的. (逻辑) 给定n = 3，结果是8，好，但是8在Quicksort中是什么意思? 解决方案为了理解您引用的书中的分析，您需要从概率理论中理解一些概念. 我们想确定QuickSort进行的平均比较数. 我们定义了一些随机变量. x_ij = 1如果比较z_i和z_j，则否则为0. X是进行比较总数的随机变量.因此x = x_ij的i和j的总和. e [x]是x的期望值，即平均值"平均值".期望是线性的，因此对总和的期望等于期望之和.这就是这本书得出的结论，比较的平均数量等于E [x_ij]的i和j的总和.由于x_ij是0或1，因此其预期值与Z_I和Z_J进行比较的概率相同. 如果您仍然遇到困难，则需要阅读概率，随机变量和预期值.

18 2023-03-23 编程技术问答社区 algorithm math computer-science clrs

二次函数的渐近紧约束

在clrs( 算法简介 Cormen，Leisoserson，Rivest和Stein)的简介，对于功能 f ( n )= an 2 + bn + c 他们说假设我们采用常数 c 1 = a /4， c 2 2 = 7 a /4， n 0 = 2·max(| b |/ a ，√(| c |/ a )). 然后0≤ c 1 n 2 ≤ sup> + bn + c ≤ c 2 n 2 对于所有 n ≥ n 0 . 因此 f ( n )是θ( n 2 ). ，但他们没有指定这些常数的价值是如何出现的? 我试图证明这一点，但不能. 请告诉我这些常数是如何出现的? 解决方案那些特定常数没有什么特别的(除了在某个n的上下文中，它们将满足f的theta theta tens.没有魔术.如果您可以找到其他正常数，该关系的关系与之同样有效(实际上，对于任何0

76 2023-03-23 编程技术问答社区 algorithm asymptotic-complexity clrs

递归矩阵乘法

我正在阅读CLR的算法简介.书显示了简单划分和征服矩阵乘法的伪代码: n = A.rows let c be a new n x n matrix if n == 1 c11 = a11 * b11 else partition A, B, and C C11 = SquareMatrixMultiplyRecursive(A11, B11) + SquareMatrixMultiplyRecursive(A12, B21) //... return C 例如，a11是a的a的子序列，该质量是n/2 x n/2的a11. 作者还暗示我应该使用索引计算，而不是创建新矩阵来表示子膜，所以我这样做了: #include #include template struct Matrix { Matrix(size_t r, size_t c) { Da

8 2023-03-22 编程技术问答社区 c++ algorithm matrix matrix-multiplication clrs

CLRS第二版中的红黑树删除修复，在Clojure中的应用

我正在为CLR 2nd Edition，第四版，第四页，第288-9页实施红黑树删除. 错误的摘要: rb-delete-fixup 如果x和w是哨兵节点，这是RB-削弱的可能结果，则评估颜色(左(w))resp. rb-耗尽固定中的颜色(右(w))在while循环的第一次迭代中遭受零指针异常. (if (and (= (get-color (get-left @w)) black) (= (get-color (get-right @w)) black)) ;; Bug here! 这个问题的所有代码都在Clojure中: ，当抛出异常时，这是红黑树状态的图: 失败的单元测试为 (deftest insert-seven-delete-three-test ... ) 在文件中 test/interval_trees/interval_tree_test.clj 这是Lein测试的输出的样子: $

18 2023-03-15 编程技术问答社区 clojure red-black-tree clrs interval-tree

如何用数组实现一个紧凑的链表？

这是练习的问题 clrs 10.3-4我正在努力解决通常希望将双链接列表的所有元素保持在存储中，例如，使用多阵列表示中的第一个M索引位置. (在分页的虚拟内存计算环境中就是这种情况.)解释如何实现该过程分配对象和自由对象，以使表示形式紧凑.假设列表本身之外的链接列表的元素没有指针. (提示:使用堆栈的数组实现.) 这是我到目前为止的解决方案 int free; int allocate() { if(free == n+1) return 0; int tmp = free; free = next[free]; return tmp; } int deallocate(int pos) { for(;pos[next]!=free;pos[next]) { next[pos] = next[next[pos]]; prev[pos] = prev[next[pos]];

0 2023-03-05 编程技术问答社区 c++ algorithm linked-list clrs

树中的一个节点是否被视为自己的祖先？

我想知道达成的共识是在计算机科学环境中的"祖先"的定义. 我只询问，因为在 incorithms介绍，第二版，p. 259有一个似乎奇数的算法Tree-Successor(x)的描述.在找到节点的继承者 x 时， [...]如果节点 x 为空，并且 x 具有成功 Y ，则 Y 是 x 的最低祖先，其左子女也是 x 的祖先. 在具有具有键2和儿童1和3的根的二进制搜索树中，1的继承者是其父级2.在这种情况下， x 是 x 的继承者 y 的左子.根据这本书的定义，然后， x 必须是自己的祖先，除非我错过了一些东西. 我在 errata 关于这个. 解决方案它只是定义的问题，但在这种情况下，是. CLRS将X的祖先定义为从根到X上的唯一路径上的任何节点，根据定义包括x. 您引用的句子片段首先通过在下一页上提到练习12.2-6，该页面指定: (回想一下，每个节点都是自己的祖先.) : - ) 其他解决方案是树中的一个节点，被认为是

90 2023-01-27 编程技术问答社区 algorithm binary-search-tree clrs

MAX-HEAPIFY中的最坏情况："最坏情况发生在树的底层正好是一半的时候"

in clrs 第三版，在第155页上，可以在Max-Heapify中进行， "the worst case occurs when the bottom level of the tree is exactly half full" 我想原因是，在这种情况下，Max-Heapify必须通过左子树"向下漂浮". 但是我无法得到的是"为什么要满一半"? 如果左子树只有一片叶子，则Max-Heapify也可以漂浮.那么，为什么不认为这是最坏的情况? 解决方案阅读整个上下文: 孩子的子树每个最多都有2n/3的大小 - 最坏的情况是当树的最后一排完全满是满一半时发生由于运行时间T(n)是通过树中的元素数(n)分析的，并且递归逐步进入了一个子树，我们需要在一个中的节点数量上找到一个上限子树，相对于n，这将产生T(n) = T(max num. nodes in subtree) + O(1) 子树中节点数的最糟糕情况是，当最后一行尽可能饱满时，另一侧

18 2022-10-30 编程技术问答社区 algorithm heap clrs

为什么一个算法的时间复杂度不考虑参数/参数的传递方式？

根据语言的不同，传递参数/参数的方式会具有不同的时间复杂度，这是不是真的.那么为什么在书籍测量时间复杂度的算法或程序中没有考虑或考虑这一点呢?CLRS 或 Mark Allen Weiss 的数据结构和算法分析永远不会增加程序总运行时参数传递方式的时间复杂度?我误解了什么吗?我知道 CLRS 是伪代码，但 Mark Allen Weiss 的算法分析显示了特定于 Java 的代码. 解决方案如果我正确理解您的问题，那么您是在问以下问题: 某些编程语言(最显着的是 C 和 C++)在按值传递(复制参数)和按指针或按引用传递(不复制参数)之间进行了区分.选择如何将参数传递给函数会改变函数完成的工作量，因为如果按值传递，则需要复制参数.然而，CLRS 根本没有谈论这个，Java 书籍也没有解决这个问题，因为它们是用 Java 编写的.这很重要，我们应该关心吗? 您是正确的，参数传递的模式绝对会影响函数运行所需的时间.例如，这里有一个用 C++ 编写的不太好的二分查找实现:

36 2022-10-08 编程技术问答社区 algorithm time-complexity clrs

我们能否使用循环不变性来证明算法的正确性，在循环不变性中，我们证明它在第一次迭代之后而不是之前是真的？

CLRS 说我们必须展示关于循环不变量的三件事: 初始化:在循环的第一次迭代之前为真. 维护:如果在循环迭代之前为真，则在下一次迭代之前保持为真. 终止:当循环终止时，不变量为我们提供了一个有用的属性，有助于表明算法是正确的. 我的问题是我可以编辑这些步骤并将它们改为: 初始化:在循环的第一次迭代之后为真. 维护:如果在循环迭代后为真，则在下一次迭代后仍为真. 终止:当循环终止时，不变量为我们提供了一个有用的属性，有助于表明算法是正确的. 说明:基本上我们使用数学归纳法来证明正确性.使用“初始化"我们证明该属性在第一次迭代后成立.使用“维护"我们可以证明该属性适用于所有迭代，因为“初始化"和“维护"一起创建了一个链.因此该属性在最后一次迭代后也保持不变. 示例: RANDOMIZE-IN-PLACE(A) 1 n ← length[A] 2 for i ← to n 3 do swap A[i] ↔ A[RANDOM(i, n)]

30 2022-10-07 编程技术问答社区 algorithm clrs loop-invariant

最大重合点

假设我们希望跟踪一组间隔中最大重叠的点——数据库中与它重叠的间隔数最多的点. 一个.证明总有一个最大重叠点是其中一个线段的端点. B.设计一个有效支持操作 INTERVAL-INSERT、INTERVAL-DELETE 和 FIND-POM 的数据结构，它返回最大重叠点.(提示:保留所有端点的红黑树.将值+1 与每个左端点关联，将值-1 与每个右端点关联.用一些额外的信息增加树的每个节点以维护最大重叠点.) 这个问题在算法简介一书中.但我不知道如何解决第二个问题.如果一个更伟大的头脑有一个优雅的解决方案，请与我分享你的想法！谢谢. 解决方案引用:http://ripcrixalis.blog.com/2011/02/08/clrs-chapter-14/ 保留所有端点的 RB 树.我们一个一个地插入端点作为从左到右扫描的扫掠线.对于每个左端点 e，关联一个值 p[e] = +1(将重叠增加 1).每个右端点 e 关联一个值 p[e] = -1(将重叠减少

46 2022-10-07 编程技术问答社区 algorithm clrs

在线性时间内打印出disjoint-set数据结构中的节点

我正在尝试在 Cormen 等人的算法简介中做这个练习，这与 Disjoin Set 数据结构有关: 假设我们希望添加操作 PRINT-SET(x)，它是给定的一个节点 x 并以任何顺序打印 x 集合的所有成员.展示如何我们可以只为不相交集中的每个节点添加一个属性森林，以便 PRINT-SET(x) 花费时间与成员数量成线性关系x的集合，以及其他操作的渐近运行时间不变.假设我们可以在 O(1) 中打印集合的每个成员时间. 现在，我很确定所需的属性是一个尾指针，因此它可以跟踪孩子. 由于不相交的集合结构已经有一个父属性，find-set(x)可以很容易地打印出一个方向的节点.但是现在有了尾指针，让我们也往另一个方向走. 但是，我不确定如何编写算法来做到这一点.如果有人能用伪代码帮助我，那将不胜感激. 解决方案每个节点都应该有一个 next 指针，指向它所在集合中的下一个节点.集合中的节点应该形成一个循环链接列表. 第一次创建单例集时，节点的next

42 2022-10-07 编程技术问答社区 algorithm time-complexity clrs disjoint-sets union-find

最大和最小的quicksort深度

这是CLR的问题(算法简介)，问题如下: 假设QuickSort的每个级别的拆分在1 -α至α的比例中，其中0 http://integrator-crimea.com/ddu0043.html 我没有如何达到此解决方案.根据链接，他们表明，最大深度为1:9的比率为log n/log(10/9)和最小log n/log(10).那么如何证明上述公式.请帮助我，因为我是算法和数据结构课程的新手，我会出错. 解决方案首先，让我们考虑这个简单的问题.假设您一个数字n和一个分数(0到1之间)p.您需要多少次将N与P相乘，以使结果数小于或等于1? n*p^k -log(n)/log(p) 现在，让我们考虑您的问题.假设您将两个部分的较短时间发送到左孩子，并将更长的时间发送给右孩子.对于最左边的链，长度是通过将\ alpha替换为上述方程中的p来给出的.对于最合适的链

8 2022-10-07 编程技术问答社区 algorithm sorting data-structures quicksort clrs

使用有偏见的随机数发生器的无偏见的随机数发生器

您有一个有偏随机数生成器，它以概率 p 生成 1，以概率 (1-p) 生成 0.你不知道 p 的值.使用它制作一个无偏随机数生成器，它以 0.5 的概率产生 1，以 0.5 的概率产生 0. 注意:此问题是 Cormen、Leiserson、Rivest、Stein 的《算法导论》中的一个练习题.(clrs) 解决方案事件 (p)(1-p) 和 (1-p)(p) 是等概率的.将它们分别取为 0 和 1 并丢弃另外两对结果，您将得到一个无偏随机生成器. 在代码中，这很简单: int UnbiasedRandom() { int x, y; do { x = BiasedRandom(); y = BiasedRandom(); } while (x == y); return x; } 其他解决方案产生一个的过程来自有偏见的无偏见硬币首先归功于冯诺依曼(一个拥有在数学和许多相关领域做

84 2022-10-07 编程技术问答社区 algorithm random probability clrs

什么是循环不变量？

我正在阅读CLR的"算法简介".在第2章中，作者提到"循环不变".什么是循环不变? 解决方案简单地说，循环不变是一些谓词(条件)，可为环路的每一个迭代而容纳.例如，让我们看一个看起来像这样的简单for循环: int j = 9; for(int i=0; i= 0 && i

32 2022-10-06 编程技术问答社区 algorithm terminology definition clrs loop-invariant

红黑树伪代码的冗余度

在算法中的第三版中，它们具有伪模型实现红黑树删除.这里是... RB-DELETE(T, z) y = z y-original-color = y.color if z.left == T.nil x = z.right RB-TRANSPLANT(T, z, z.right) elseif z.right == T.nil x = z.left RB-TRANSPLANT(T, z, z.left) else y = TREE-MINIMUM(z.right) y-original-color = y.color x = y.right if y.p == z x.p = y //

358 2022-07-19 编程技术问答社区 algorithm red-black-tree clrs

对CLRS随机构建的二进制搜索树证明中的索赔感到困惑

不确定我是否应该把它放在数学stackexchange上，但哦好. 在clrs ... 的第300页 Theorem 12.4 The expected height of a randomly built binary search tree on n distinct keys is O(lgn). 它们定义了3个随机变量... 'Xn' is the height of a randomly built binary search on n keys. 'Yn' is the "exponential height", where Yn = 2^(Xn) 'Rn' is the position that the root key would occupy if the key's were sorted, its rank. 和指示器随机变量Zn,1 Zn,2 Zn,3 ... Zn,n ... 'Zn,i = I{Rn = i}' 所以他们继续

492 2022-07-19 编程技术问答社区 algorithm binary-tree binary-search clrs

以线性时间打印出Disjoint Set中的节点

我正在尝试通过Cormen等人进行算法介绍算法，它与Disjoin设置数据结构有关: 假设我们希望添加给出的操作打印集(x) 节点X并按任何顺序打印x集的所有成员.展示如何我们可以将单个属性添加到脱消集中的每个节点森林使打印集(X)在成员数量中需要时间线性 X的集合和其他操作的渐近运行时间不变.假设我们可以在O.1/中打印集合的每个成员时间. 现在，我很确定所需的属性是尾部指针，所以它可以跟踪孩子们.由于Disjoint Set结构已经具有父属性，因此查找设置(x)可以轻松打印出一个方向的节点.但现在，有一个尾针，让我们除了另一个方向. 但是，我不确定如何将算法写入算法来执行此操作.如果有人能够在伪代码中嘿嘿，那将非常感谢. 解决方案每个节点应该具有到它所在的集合中的下一个节点的next指针.集合中的节点应形成循环链接列表. 首次创建单例设置时，节点的next指针指向自身. 当您使用节点X设置设置并使用节点设置Y(并且您已经检查了这些集合通过归一

3500 2022-07-19 编程技术问答社区 algorithm time-complexity asymptotic-complexity disjoint-sets clrs

什么是循环不变量？

我正在阅读“算法简介"CLRS.作者在第 2 章(插入排序)中讨论了循环不变量.我不知道这意味着什么. 解决方案简单来说，循环不变量是对循环的每次迭代都成立的谓词(条件).例如，让我们看一个简单的 for 循环，如下所示: int j = 9; for(int i=0; i= 0 && i = 0.

302 2022-07-17 编程技术问答社区 algorithm data-structures clrs loop-invariant