GESP 八级 · GESP 202406 C++ 八级 第 21 题

在 $N$ 个元素的二叉排序树中查找一个元素，最差情况的时间复杂度是 $O(\log N)$。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】二叉排序树｜时间复杂度｜最坏情况

🎯 考纲定位

GESP 八级 C++《数据结构与算法》模块，命题人专门卡住考生对"二叉排序树"与"平衡二叉树"的概念混淆。绝大多数人看到 BST 就默认是平衡的，忘了普通 BST 最坏退化成链表。