lyp123

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

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