标签: clrs

我正在阅读CLRS的"算法简介".在第2章中,作者提到了"循环不变量".什么是循环不变量？

你有一个有偏差的随机数发生器,它产生概率为1的1和概率为1的0(1-p).你不知道p的值.使用它可以产生一个无偏的随机数发生器,它产生1的概率为0.5和0,概率为0.5.

注意:这个问题是Cormen,Leiserson,Rivest,Stein的算法导论中的一个练习问题.(clrs)

在CLRS,第三版,第155页,给出了在MAX-HEAPIFY中,

"the worst case occurs when the bottom level of the tree is exactly half full"  

我想原因是在这种情况下,Max-Heapify必须通过左子树"向下浮动".
但我无法得到的是"为什么半满"？
如果左子树只有一个叶子,Max-Heapify也可以向下浮动.那么为什么不把这视为最坏的情况呢？

在"算法简介,第3版"练习24.3-5中想要一个例子,这是错误的(并非总是如此).那可能吗？在我看来,这是不可能的,因为在已经确定当前顶点的路径时,每个边都放松了.

一字一字:

N. N.教授声称有一个Dijkstra算法正确性的证明.他声称Dijkstra算法按照它们在路径上出现的顺序放宽图中每条最短路径的边缘,因此路径松弛属性适用于从源可到达的每个顶点.通过构建有向图来显示教授是错误的,Dijkstra的算法可以无序地放松最短路径的边缘.

在Algorithms Third Edition的介绍中,他们有一个红黑树删除的伪代码实现.这里是...

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       // <--------- why????
        else
                RB-TRANSPLANT(T, y, y.right)
                y.right = z.right
                y.right.p = y
        RB-TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y
        y.color = z.color
    if y-original-color == BLACK
        RB-DELETE-FIXUP(T, x)

TREE-MINIMUM只找到树中的最小值,RB-TRANSPLANT取第二个参数的父级,并指向第三个参数,第三个参数的父级是第二个参数的父级. …

在CLRS(Cormen,Leiserson,Rivest和Stein的算法导论)中,用于函数

˚F(Ñ)= 一个² + BN + Ç

他们说

假设我们取常数c ₁ = a/4,c ₂ = 7 a/4,并且n ₀ = 2·max(| b |/a,√(| c |/a)).
然后0≤ c ^ ₁ ñ ² ≤ 的² + BN + c ^ ≤ c ^ ₂ Ñ ²对于所有Ñ ≥ Ñ ₀.
因此f(n)是Θ(n ²).

但他们没有具体说明这些常数的价值是如何产生的？
我试图证明它但不能.
请告诉我这些常数是怎么来的？

我被作为家庭作业的算法导入练习11.1-3,如下:

建议如何实现直接访问表,其中存储元素的键不需要是不同的,并且元素可以具有卫星数据.所有三个字典操作(插入,删除和搜索)都应该在O(1)时间内运行.不要忘记Delete将一个指向要删除的对象的指针作为参数,而不是键.

好吧,Insert没有问题,因为它只是意味着在表中的适当位置创建一个链表(如果它还不存在)并向其添加元素.给定键的搜索可以返回与键匹配的任何元素,因此它只是意味着我们需要返回表中匹配列表的头部.

我的问题是删除操作.如果我修改对象添加到链接列表中指向其节点的指针,那么我可以在O(1)中删除,但我不确定我是否可以更改对象.有没有办法在不改变给定对象的情况下这样做？

我想知道在计算机科学背景下对"祖先"定义的共识是什么.

我只是问,因为在算法导论,第二版,p.259有一个Tree-Successor(x)看似奇怪的算法的描述.在寻找节点x的后继者时,

[...]如果节点的右子树X是空的,X有一个继任Ÿ,然后ÿ是最低的始祖X,其左子也是祖先X.

在具有关键根二叉搜索树2和孩子1和3,的继任者1是其母公司2.在这种情况下,x是x的后继者y的左子.根据这本书的定义,x必须是它自己的祖先,除非我遗漏了什么.

关于这一点,我没有在勘误表中找到任何内容.

是的,这将是一项家庭工作(我自学而不是大学)问题,但我不是要求解决方案.相反,我希望澄清问题本身.

在CLRS第3版,第593页,消费税22.1-5,

有向图的平方G =(V,E)是图G ^ 2 =(V,E ^ 2),使得(u,v)∈E^ 2当且仅当G包含具有至多两个的路径时 u和v之间的边缘.描述用于从G的邻接列表和邻接矩阵表示中计算G2的有效算法.分析算法的运行时间.

但是,在CLRS第2版(我找不到书籍链接),第530页,相同的消费税,但略有不同的描述:

有向图G =(V,E)的平方是图G ^ 2 =(V,E ^ 2),使得(u,w)∈E^ 2当且仅当某些v∈V时,两者( u,v)∈E和(v,w)∈E.即,只要G包含u和w之间恰好有两条边的路径,G ^ 2就包含u和w 之间的边.描述用于从G的邻接列表和邻接矩阵表示中计算G ^ 2的有效算法.分析算法的运行时间.

对于具有"正好两个边缘"的旧消费税,我可以理解并且可以解决它.例如,对于邻接列表,我只做v-> neighbour-> neighbour.neighbour,然后将(v,neighbour.neighbour)添加到新的E ^ 2.

但对于"最多两个边缘"的新消费税,我很困惑.

"当且仅当G包含u和v之间最多两条边的路径时"是什么意思？

由于一条边可以满足条件"最多两条边",如果u和v只有一条只包含一条边的路径,我应该将(u,v)加到E ^ 2吗？

如果u和v有一条带有2条边的路径,但是还有另一条带有3条边的路径,我可以将(u,v)添加到E ^ 2吗？

给定:整数数组值K,M

问题:找到我们可以从给定数组的所有K个元素子集中获得的最大总和,使得和小于值M？

是否存在可用于此问题的非动态编程解决方案？或者如果它只是dp [i] [j] [k]只能解决这类问题!你能解释一下算法吗？