python-3.x - 这个算法是 O(1) 还是 O(n) 空间复杂度

Question

我有一个家庭作业问题，要求我在时间复杂度为 O(n) 和空间复杂度为 O(1) 的程序中找到一个缺失的数字。

我觉得我对什么构成了 O(1) 空间复杂度有了很好的理解，但是我不确定将一个变量赋给给定数组中的最大值是否会使它成为 O(n) 空间复杂度。下面的代码是我专门写的

def findMissing(A):
    greatest = 0
    for i in range(len(A)):
        if A[i] > greatest:
            greatest = A[i]

我认为它仍然是 O(1)，因为我试图保留的 O(n) 是包含最大值以及所有其他值的完整数组，但同时我的变量仍然与输入大小有关，所以我不确定。

Answer 1

由于您的代码在数组中循环一次，因此它的时间复杂度为 O(n)。存储仅维护 1 个变量，因此它具有 O(1) 空间复杂度。我假设您为了这个问题而放弃了 return 语句，否则，请确保您也包含了它。