clrs

0热度

2回答

从Java的约Hashtable类的文档，它说作为一般规则，默认加载因子（.75）因此加载时间和空间成本上寻求一种折衷Hashtable的因子是0.75，这意味着如果有N个密钥，Hashtable将使用M = N/0.75个空间来存储它们。在CLRS书中，它还引入了负载因子alpha。但是从我的理解来看，CLRS打算设置大于1的α，即M = N/alpha < N.这意味着Hashtable

2热度

1回答

什么是直觉behing的最优子？

这个问题是从CLRS PG 362 整体最佳的解决方案结合了两个相关的子问题的最佳解决方案相关的动态规划和具体杆切削的问题。整体最佳解决方案是通过寻找最佳的解决方案，以个别子问题，然后以某种方式俱乐部他们。我无法理解直觉和概念。任何链接，例子？感谢

3热度

1回答

最大重叠点

假设我们希望跟踪一组间隔中的最大重叠点 - 数据库中具有最大间隔数的点与其重叠。 a。显示总是有一个最大重叠点，它是其中一个段的终点。 b。设计一个有效支持INTERVAL-INSERT，INTERVAL-DELETE和FIND-POM操作的数据结构，它返回最大重叠点。（提示：保留所有端点的红黑树，将值+1与每个左端点相关联，并将值-1与每个正确的端点相关联。使用一些额外信息增加树的每个节点以维

2热度

2回答

为什么17612864的14个最重要的位是67？

在CLRS的第264页的底部，作者说在获得r0 = 17612864之后，r0的14个最高有效位产生散列值h（k）= 67。我不明白为什么它给出了67，因为67以二进制是1000011这是7位。 EDIT 在教科书：作为一个例子，假设我们有K = 123456，P = 14，M = 2^14 = 16384，以及w = 32适应Knuth的建议，我们选择A是（\ sqrt（5） - 1）/ 2最

2热度

1回答

为什么我们不在红黑树插入中添加黑节点而不是红节点？

在红黑树插入，我们总是选择添加一个新的节点为红色，以便我们能够避免改变树的黑色高度。为什么这比添加黑节点更可取？

3热度

1回答

编码的输入（时间复杂度）

不知道这是否是正确的地方问这个问题。在Cormen的第1056页我读到，如果一个算法的运行时间是O（k）并且“k”以一元表示，即一串k 1s，那么该算法的运行时间是0（n），其中“n”是输入大小为比特，如果“k”表示为二进制，则n = lg k + 1，算法的运行时间变为o（2^n）。所以，我的疑问是，为什么在这种情况下“一元”表示不会被优先选择，因为它在多种情况下给出多项式时间，而在其他情况

3热度

1回答

中位数选择算法 - 是否找到绝对中位数，或“中位数中位数”接近绝对中位数？

CLRS第3版中的9.3节“在最差情况下线性时间选择”讨论了“选择”算法（有时称为BFPRT算法，归因于Blum，Floyd，Pratt，Rivest和Tarjan），用于查找列表的中位数在最坏情况下在O（n）时间。当我试图在白板上运行示例时，我感到有点困惑。我知道每次调用“Select”时都可以消除一定数量的元素（我读过的30％已被淘汰，而70％需要再次检查），但我感到困惑的是数组的哪一部分可以

2热度

3回答

递归矩阵乘法

我正在阅读CLRS算法简介。书示出了用于简单分伪代码而治之矩阵乘法： 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) + Square

1热度

1回答

分析

我被Cormen等读取推流算法在算法导论我具有其中提到如下理解引理26.20 difficulaty：设G =（ V，E）是具有源s和宿t的流网络，并且假设在G中是预流。然后，对于任何溢出顶点u，在残差网络Gf中存在从u到s的简单路径。要查看此leema的上下文可以在以下链接找到。 http://integrator-crimea.com/ddu0164.html 请您在此understad

0热度

1回答

动态集合中的后继和前代最坏情况运行时间

以下动态集合运算的渐近最差情况运行时间是多少？后续（L，X）为未分选的单独&双向链表前身（L，X）为未排序双向链表 L：列表中，x：指针的条目（其实这是本书第10-1题的一部分：“算法导论，第三版”，我搜索了答案，答案是O（n），但我找不到任何解释）