最优二叉搜索树 - Cormen
Optimal binary search tree - Cormen
我正在研究 Cormen 等人的算法简介中的最优二叉搜索树。作为参考，我附上了 text link。
在第 399 页，我们有 table 有贡献。我无法理解作者如何计算此专栏。例如节点k1的贡献是0.30，k4是0.20。作者是如何计算的？
看公式得到T中的搜索成本=> E[T中的搜索成本]=....（第398页底部）
获取 k1 的费用：
k1=(depth(k1) + 1) * p1
查看 table 的深度值 (k1) 和 p1 （第 399 页）。
k1=(1+1)*0.15
=2*0.15
=0.3
k2=(0+1)*0.10
=1*0.10
=0.10
etc
希望我的解释能帮到你
我正在研究 Cormen 等人的算法简介中的最优二叉搜索树。作为参考，我附上了 text link。
在第 399 页，我们有 table 有贡献。我无法理解作者如何计算此专栏。例如节点k1的贡献是0.30，k4是0.20。作者是如何计算的？
看公式得到T中的搜索成本=> E[T中的搜索成本]=....（第398页底部）
获取 k1 的费用：
k1=(depth(k1) + 1) * p1
查看 table 的深度值 (k1) 和 p1 （第 399 页）。
k1=(1+1)*0.15
=2*0.15
=0.3
k2=(0+1)*0.10
=1*0.10
=0.10
etc
希望我的解释能帮到你