有序链表二分查找的时间复杂度：O(N)还是O(NlogN)？

首先直接给结论：如果按照你假设的“每次定位中间节点都需要O(N)时间”，第二种计算方式是正确的，时间复杂度为O(NlogN)。下面拆解逻辑，帮你搞清楚为什么第一种思路错了，以及实际场景下的真实复杂度。

为什么不能把logN视为常数？ #

大O表示法的核心是描述算法运行时间随输入规模N增长的变化趋势。这里的“常数”指的是不随N变化的固定值——比如不管N是10还是100万，这个值都保持不变。但logN是N的函数：当N从1000涨到100万时，log₂(N)会从10变成20，它会随着N的增大而增长（虽然增长速率很慢）。因此，logN属于“随N变化的项”，不能被当成常数忽略。所以logN * O(N)不能简化为O(N)，而应该是O(NlogN)。

实际场景下的真实复杂度（补充） #

你假设的“每次定位中间节点都需要O(N)时间”其实是一种不够优化的做法。在实际实现链表二分查找时，我们不需要每次都从头遍历整个链表找中间节点，只需要遍历当前搜索区间的一半：

• 第一次找中间：从表头走到第N/2个节点，耗时O(N/2)
• 第二次搜索区间长度变为N/2，找中间耗时O(N/4)
• ……
• 最后一次区间长度为1，耗时O(1)

把这些时间加起来是一个等比数列求和：
N/2 + N/4 + N/8 + ... + 1 = N - 1
这个总和的时间复杂度是O(N)，这才是链表二分查找的真实时间复杂度。但如果真的每次都从头遍历整个链表找中间，那时间复杂度确实是O(NlogN)。

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