这些天在补课上落下来的知识,有在看算法导论,算法导论里面只是解释了为什么这个算法的时间复杂度等于那些,并没有提到为啥这样,看了其他博主的讲解,有人说里面的mark只是单纯地为了摊还分析,我觉得并不尽然,下面给出我的理解。


  开门见山,图一中在算法导论第三版里面的证明时间复杂度的时候,在一开始先证明了yi.degree>=i-2这个式子在图二的引理19.4里面起到了决定性的作用而最终的推论正是来自于引理19.4,不难看出正是因为19.1里面的限制才能有后面的x.degree<lgn,才能有最终的结果,所以不难看出这个mark的作用从表面上来看是级联切割,但是在级联切割的时候也同样在保证一个树的一个秩序,换句话说,就是不要让这个树的度数按照某个规约来,这样的话,可以使得这个堆不至于会出现某一颗树特别高的情况,保证每一个节点都能有相应大的度数在,这样在操作堆的时候,这个堆就会有相当好的一个时间复杂度。

引理19.1

图一

引理19.4

图二