算法导论思考题 18-2 连接与分裂 2-3-4 树
由 瞳人
发布于 April 7, 2017, 10:03 p.m.
4 个评论
题目
略
答案
网上的多数中文答案有不对的地方（包括参考链接中的中文博客），所以在这里简单记录一下。
c) \[h(T'_{i-1}) \geqslant h(T'_{i})\]
d) \[\sum^m_{i=1}(1+|h(T'_{i-1})-h(T'_{i})|)=m+\sum^m_{i=1}(h(T'_{i-1})-h(T'_{i}))=m+h(T'_{0})-h(T'_{m}) \in O(\lg n)\]
其中求和项来自于 b) 结论，第一个等号去掉绝对值符号，可由 c) 结论得。
参考链接
- https://walkccc.gitbooks.io/clrs/content/Chap18/18-2.html
- https://parasol.tamu.edu/~welch/teaching/629.f03/hw2sol.pdf
- http://blog.csdn.net/zilingxiyue/article/details/44983919
- http://www.cnblogs.com/null00/archive/2012/07/06/2578492.html
test April 10, 2017, 10:56 a.m. | Reply
0
4 Comments