数据结构：二叉搜索树的查找时间复杂度 作者：马育民 • 2022-07-06 10:58 • 阅读：10437 需要掌握：[二叉搜索树的高度](https://www.malaoshi.top/show_1IX3ctTefutk.html "二叉搜索树的高度") # 说明 平衡情况下，时间复杂度是 `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₂n` 和 `logn` **计算的结果是不等的**，但在比较算法的复杂度的时候，取对数的底数必须一样才有可比性，所以这种写法只是 **方便比较** #### 参考 https://blog.csdn.net/zhangjin1120/article/details/121237377 原文出处：http://malaoshi.top/show_1IX3cuEhaM1S.html