算法复杂度 - p=(p-1)/2 算法分析

问题描述

问 题

刚学二叉堆,想知道它插入的复杂度,于是想自己动手算一下,但是却发现下不了笔....
于是希望有人帮我写下这个分析过程,详细点,一步步列出,谢谢.

p=(p-1)/2,p<0需要多少步

解决方案

一棵有N个节点的完全二叉树不大于Log(N)，证明略

含有N个元素的二叉堆插入元素只需要不超过Log(N)+1次比较，因为插入元素时是把元素插入到完全二叉数的最后一个元素，最坏情况下只需要上浮到树根的位置。树的高度不大于Log(N)，因此。。。

这篇关于算法复杂度 - p=(p-1)/2 算法分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！