递归实现名人查找算法的空间复杂度是否真的为O(1)？

结论 #

你的判断完全正确，这段代码的额外空间复杂度为O(N)。

原因说明 #

• 递归栈开销是核心占用：核心递归函数findPotentialCelebrity属于线性递归，输入规模为N时，递归调用链会从n=N逐层深入到n=0的基准分支，递归栈的深度固定为N，每一层栈帧存储的参数、临时变量都是常数级大小，单这部分的空间开销就达到O(N)量级。
• 其他辅助变量均为常数级：除递归栈外，代码中用到的其他临时变量（校验阶段的c1、c2、循环变量i等）的存储开销都不会随N增长，不会影响空间复杂度的量级。

你可能未考虑到的特殊情况 #

• 尾递归优化的例外：如果使用支持尾递归优化的编程语言（如Scheme、Erlang），且代码调整为符合尾递归要求的写法，可以将递归栈的开销压缩到O(1)，但有两个前提你当前场景不满足：第一，当前的递归写法不是尾递归（递归调用返回后还有多分支判断逻辑），第二，Python官方解释器没有实现尾递归优化，所以在Python环境运行这段代码，当N足够大时一定会触发栈溢出。
• 空间复杂度统计口径差异：如果统计规则要求包含输入数据本身的存储开销，那么存储人际关系矩阵需要O(N²)的空间，但常规算法复杂度分析默认只计算算法执行产生的额外开销，输入本身的占用不算在内，所以通用统计口径下还是O(N)。

修正后可直接运行的代码 #

# Person with 2 is celebrity
MATRIX = [[0, 0, 1, 0],
           [0, 0, 1, 0],
           [0, 0, 0, 0],
           [0, 0, 1, 0]]
 
 
def knows(a, b):
    return MATRIX[a][b]
 
# Returns -1 if a potential celebrity
# is not present. If present,
# returns id (value from 0 to n-1).
def findPotentialCelebrity(n):
    # Base case
    if (n == 0):
        return 0
 
    # Find the celebrity with n-1
    # persons
    id_ = findPotentialCelebrity(n - 1)
 
    # If there are no celebrities
    if (id_ == -1):
        return n - 1
    # if the id knows the nth person
    # then the id cannot be a celebrity, but nth person could be one
    elif knows(id_, n - 1):
          return n - 1
    # if the nth person knows the id
    # then the nth person cannot be a celebrity, but id could be one
    elif knows(n - 1, id_):
          return id_
    # If there is no celebrity
    return -1
 
# Returns -1 if celebrity
# is not present. If present,
# returns id (value from 0 to n-1).
# a wrapper over findCelebrity
def Celebrity(n):
    # Find the celebrity
    id_=findPotentialCelebrity(n)
 
    # Check if the celebrity found is really the celebrity
    if (id_ == -1):
        return id_
    else:
        c1=0
        c2=0
 
        # Check the id is really the celebrity
        for i in range(n):
            if (i != id_):
                c1 += knows(id_, i)
                c2 += knows(i, id_)
 
        # If the person is known to everyone
        if (c1 == 0 and c2 == n - 1):
            return id_
        return -1
 
# Driver code
if __name__ == '__main__':
    n=4
    id_=Celebrity(n)
    if id_ == -1:
        print("No celebrity")
    else:
        print("Celebrity ID", id_)

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