如何判断哪些函数的时间复杂度为O(log n)

你之前对O(n)、O(n²)、O(n³)这类复杂度的判断方法是对的：嵌套几层循环，大概率就是n的几次方复杂度。O(log n)的判定不能用循环层数来套，核心看迭代过程中问题规模的变化规律：

• 核心判定逻辑：只要循环每次执行，都会把待处理的问题规模按固定比例缩小，不管缩小的比例是1/2、1/3还是其他固定值，这段循环的时间复杂度就是O(log n)

最典型的例子就是有序数组的二分查找，示例代码如下：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        # 每次取中间位置，直接筛掉一半不匹配的元素
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

上面的代码每次循环都会把搜索范围缩小为原来的1/2，假设数组长度是n，最多需要循环的次数就是log₂n，大O表示法会忽略对数的底数，所以统一标记为O(log n)。

• 常见的O(log n)场景包括：有序数组的二分查找、二叉搜索树的元素查询、堆的插入/弹出操作、快速幂计算等，这些逻辑都不需要遍历所有元素，每次操作都能淘汰固定比例的无效数据

你也可以用代入法快速验证：当n的取值翻倍时，O(log n)逻辑的执行次数只会增加1次，执行次数的增长速度远慢于n本身的增长速度，和O(n)每次n翻倍执行次数也翻倍的特征有明显区别。

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