时间戳

首页 > 解决方案 > 这个函数的大 O 时间是多少（来自 LeetCode 的加一个问题）

python - 这个函数的大 O 时间是多少（来自 LeetCode 的加一个问题）

问题描述

我只是想通过我的 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 最终都被翻转，然后为新位置创建新数组。

标签： pythonalgorithmtime-complexitybig-o

解决方案

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

但就像 chepner 所说，这里的迭代会更好。并且要摆脱 Ariel A，而不是try except检查是否place + 1超出索引范围的块，您可以使用

if place + 1 >= len(digits)

推荐阅读