这个函数的大O时间是多少（加LeetCode的一道题）

Question

我只是想通过我的 leetcode 解决方案中的大 O 来练习推理。

这是我对名为“Plus One”的问题的解决方案。我只是想知道大 O 时间是什么时候。我的想法和笔记附在代码中

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        def incrementer(digits,place):
            if (digits[-place] != 9):              # My base case
                digits[-place] = digits[-place] + 1
                return digits
            else:
                try:
                    next = digits[-place-1]
                except IndexError:
                    digits = [0]*(place+1) # This takes O(n) time?
                    digits[0] = 1
                    return digits
                digits[-place] = 0
                # Recursive case
                return incrementer(digits,place+1) # Recursive Case # O(n)?

        return incrementer(digits,1)

我相信这会导致 O(n^2) 更糟，因为这意味着它会遍历整个数组，然后创建一个大小为 n + 1 的新数组，其中填充了 0。我的想法是否正确？对于像 9999999 这样的数字，会发生这种情况，其中所有 9 最终都会翻转，然后为新位置创建新数组。

Answer 1

你说的不太对，但是很接近；在 Python、array creation is O(n) 中，并且在最坏的情况下要到达该行，您需要遍历整个列表，这也是 O(n)。所以你有 O(n + n) 也就是 O(2n)（但是我们丢弃了乘数，所以我们会再次将其归类为 O(n)）。

但正如 chepner 所说，迭代会更好。为了摆脱 Ariel A，您可以使用

而不是 try except 块来检查 place + 1 是否超出索引范围

if place + 1 >= len(digits)

Answer 2

我让你的代码不那么复杂，因为你可以看到只有一个 while 循环，这意味着 O(n) 时间复杂度：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits) - 1
        while n >= 0:
            if digits[n] != 9:
                digits[n] += 1
                return digits
            else:
                digits[n] = 0
                n -= 1
        return [1] + digits

这个函数的大O时间是多少（加LeetCode的一道题）

What is the big O time of this function (Plus One question from LeetCode)

python

algorithm

big-o

time-complexity