算法性能与数据结构查询问题咨询（含自我解答修正请求）

问题1：首次运行算法A比B快，第二次却相反的原因及举例 #

你的思路方向是对的，我来把时间复杂度的实际差异讲得更具体些：

• 第一次运行时，算法B需要完成排序+二分搜索的完整流程：排序的时间复杂度是O(n logn)，加上二分搜索的O(logn)，总耗时是O(n logn)量级；而算法A是线性搜索，时间复杂度O(n)。当n不是极大的时候，O(n)的实际运行耗时会比O(n logn)更短——比如n=1000时，线性搜索最多执行1000次比较，而快速排序大概要做1000*log₂(1000)≈10000次操作，再加上10次二分搜索，总操作数远多于线性搜索，所以第一次A更快。
• 第二次运行时，数据集已经被算法B排好序了，此时B不需要再执行排序步骤，直接用二分搜索就能完成查找，耗时仅O(logn)；而算法A不管数据是否有序，都还是要逐个遍历，耗时O(n)。还是拿n=1000举例，二分搜索只需要10次左右的比较，远少于线性搜索的1000次，所以第二次B更快。

对应的算法例子完全符合你的设定：

• 算法A：线性搜索（遍历每个元素直到找到目标）
• 算法B：先快速排序再二分搜索（首次运行需排序，后续复用有序数据集）

问题2：有序链表与最小高度BST查找最大值的效率对比 #

你的链表部分分析很准确，我再补充BST的情况，就能完成完整对比了：

• 对于有序链表：
  • 如果链表带有尾指针，直接访问尾节点就能拿到最大值，时间复杂度O(1)；
  • 如果没有尾指针，需要从表头遍历到表尾，时间复杂度O(n)。
• 对于最小高度BST：
  最小高度BST是平衡二叉搜索树，其高度为floor(log₂n)+1。在BST中，最大值一定位于最右侧的叶子节点，查找时只需要沿着树的右分支一直向下走，直到没有右子节点为止，这个过程的时间复杂度是O(logn)。

所以最终的快慢对比分两种情况：

• 当有序链表有尾指针时：链表查找最大值O(1)的效率远高于BST的O(logn)；
• 当有序链表无尾指针时：BST的O(logn)效率比链表的O(n)更快。

内容的提问来源于stack exchange，提问作者user3002108