数据结构:二叉搜索树的查找时间复杂度

需要掌握:二叉搜索树的高度

说明

平衡情况下,时间复杂度是 O(logn)

退化成链表,只有左子树 或 右子树,时间复杂度是 O(n)

计算过程

二叉搜索树的查找的时间复杂度,与树的高度相同,平衡情况下,高度是 log2(n)+1,时间复杂度是 log2(n)+1

解释:log2(n) 取整数,丢弃小数,不是四舍五入

时间复杂度的三个原则:

  1. 如果运行时间是常数量级,用常数1表示;
  2. 只保留时间函数中的最高阶项;
  3. 如果最高阶项存在,则省去最高阶项前面的系数。

第一次简化

根据原则2,所以 log₂n+1,就简化为 log₂n

第二次简化

根据换底公式:log a(b) = log c(b) / log c(a),可知:

log₂n = log c(n) / log c(2)

c 可以是任意数字,所以 1 / log c(2) 是常数,可去掉

log c(n) 简化成 log n

结果

O(log n)

简化后的计算结果

log₂nlogn 计算的结果是不等的,但在比较算法的复杂度的时候,取对数的底数必须一样才有可比性,所以这种写法只是 方便比较

参考

https://blog.csdn.net/zhangjin1120/article/details/121237377


原文出处:https://malaoshi.top/show_1IX3cuEhaM1S.html