Python递归中列表切片与索引实现的复杂度对比

用列表切片编写递归函数，在时间和空间复杂度上确实存在明显劣势，这也是主流递归实现更偏爱low/high索引方式的核心原因。

时间复杂度对比 #

• 索引版（binSearch2）：每次递归仅做O(1)的计算（计算mid、元素比较），递归深度为O(log n)，整体时间复杂度保持二分查找的最优O(log n)。
• 切片版（binSearch）：Python的列表切片操作（如arr[mid+1:]）会创建全新的子列表，这个操作的时间开销是O(k)（k为子列表长度）。每次递归都会生成一个约为原列表一半长度的新列表，所有递归步骤中创建的子列表总长度为n + n/2 + n/4 + ... ≈ 2n，整体时间复杂度退化为O(n)，完全失去了二分查找的性能优势。

空间复杂度对比 #

• 索引版：递归调用栈深度为O(log n)，仅需存储low、high、mid几个整数变量，额外空间复杂度为O(log n)。
• 切片版：除了O(log n)的递归栈开销，每个递归调用都会创建新的子列表，这些子列表的总空间开销为O(n)，整体空间复杂度升至O(n)，远高于索引版。

两种实现代码示例 #

列表切片实现

def binSearch(arr,k):
    if len(arr) < 1:
        return -1
    mid = len(arr) // 2
    if arr[mid] == k:
        return mid
    elif arr[mid] < k:
        val = binSearch(arr[mid+1:],k)
        if val == -1:
            return -1
        else:
            return mid + 1 + val
    else:
        return binSearch(arr[:mid],k)

索引实现

def binSearch2(arr,k,low,high):
    if low > high:
        return -1
    mid = (high+low) // 2
    if arr[mid] == k:
        return mid
    elif arr[mid] < k:
        return binSearch2(arr,k,mid+1,high)
    else:
        return binSearch2(arr,k,low,mid-1)

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