python - 这个程序的空间复杂度真的是 O(1) 吗？

Question

我今天遇到了奇怪的信息。我会说这段代码的空间复杂度是 O(N)。每次递归发生时，都会创建一个新的堆栈帧。并且递归调用的数量与矩阵的大小成正比（在本例中为 4）。我是对的还是我什么都没看到？

顺便说一句，这里的问题是找到名人（每个人都认识他们，但他们不认识任何人）。我们有矩阵所需的信息，1 表示知道，0 表示不知道。例如，人 0 不认识人 1，但认识人 2。

 # 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 on
    elif knows(id_, n - 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(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_)

标签： pythonrecursionspace-complexity