这个算法是 O(1) 还是 O(n) space 复杂度

Question

我有一道作业题要求我在时间复杂度为 O(n) 且程序复杂度为 O(1) space 的数组中查找缺失的数字。

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

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) space 复杂度。我假设你为了这个问题而放弃了 return 声明，否则，请确保你也包含它。