平衡二叉搜索树查找的时间复杂度为什么是O(log n)? |
您所在的位置:网站首页 › 二叉树复杂度如何计算出来 › 平衡二叉搜索树查找的时间复杂度为什么是O(log n)? |
二叉搜索树的搜索的时间复杂度,会因为具体结构不同而不同,只有右子树的情况下,时间复杂度是O(n)。平衡的情况下,时间复杂度是O(logn)。这个O(logn)是怎么来的?
n个结点的二叉搜索树的高度是多少?
只有1个根节点的二叉搜索树,高度为1。log2(1)=0,0+1=1;2,3个结点的二叉搜索树,高度为2。log2(2)=1,1+1=2;4,5,6,7个结点的二叉搜索树,高度为3。log2(7) < 3,log2(7)取整+1为3。N个结点的二叉搜索树,高度是[log2(N)]+1。[]表示取整。
查找的最坏情况
先说说最好情况,最好情况就是,要查找的那个数刚好是根节点,只需要查找1次。最坏情况,要查找到树的最深节点,查找次数是树的高度。根据上面所讲,树的高度就是[log2(n)]+1。 我们平常所说的时间复杂度,是指最坏时间复杂度。因为平均时间复杂度和最坏时间复杂度很接近,所以就直接考虑最坏时间复杂度。对这一点有疑问,参考:算法(一)时间复杂度。 由此,我们可以确定O(n)=[log2(n)]+1 时间复杂度的三个原则: 如果运行时间是常数量级,用常数1表示;只保留时间函数中的最高阶项;如果最高阶项存在,则省去最高阶项前面的系数。 由于只保留最高阶项,所以[log2(n)]+1,就简化为[log₂n]了。对于取整符号[],在计算机中就是乘以10,再除以10,例如: 3.6*10/10=3 //这是计算机中的运行结果,不是数学中的计算结果。数学结果还是3.6 所以,[log₂n]=log₂n*10/10,根据原则三,省去最高阶想前面的系数,就是log₂n。 log₂n也不是log n呀?为什么时间复杂度中的描述用“logn”,而不用“log₂n”、“lnn”或“lgn”?打破砂锅问到底。 看看换底公式: 把换底公式用在og₂n上,如下图: 可以看到,在去掉常数的情况下,log₂n可以是 l o g 3 n log_3n log3n(这个对数函数,看上去是不是很帅?MarkDown 数学公式),也可以是 l o g 4 n log_4n log4n,所以2也省点了,就是logn。感谢:ChanXB1n给我提供的思路。 总结一下二叉搜索树的查找,最坏情况就是目标结点位于最深的叶子结点,就是树的高度[ l o g 2 n log_2n log2n]+1,去掉常数项,去掉取整运算,再根据换底公式去掉对数的底数,就得到了O(logn)。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |