首页 > 试题广场 >

通过改变位势函数能够证明展开的不同的界。令权函数W（i）为指

[问答题]

通过改变位势函数能够证明展开的不同的界。令权函数W（i）为指定给树中每个节点的某个函数，令S(i)为以i为根的子树上所有节点（包括节点i本身）的权的和。对于与用在展开界的证明中的该函数相对应的所有的节点，特殊情况为W(i)=1.令N为树中节点的个数，并令M为访问的次数。证明下列两个定理：

a. 总的访问时间是O(M+(M+N)logN)。

b. 如果q_i为项i被访问的次数，而对所有的i，q_i>0，那么总的访问时间为: $O(M+\sum_{i=1}^{N}{q_{i}log(M/q_{i}}))$

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小

难度：

0条回答 0收藏 286浏览

扫一扫，把题目装进口袋