이 함수의 큰 O 시간은 얼마입니까 (LetCode의 Plus One 질문)

Question

나는 내 leetcode 솔루션의 큰 O를 통해 추론을 연습하려고합니다.

이것이 " 플러스 원 " 이라는 문제에 대한 나의 해결책 입니다. 나는 단순히 Big 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)

나는 이것이 전체 배열을 통과하고 0으로 채워진 크기 n + 1의 새로운 배열을 생성했음을 의미하기 때문에 이것이 O (n ^ 2) 더 나빠질 것이라고 믿습니다. 이 생각이 맞습니까? 이것은 9999999와 같은 숫자에 대해 발생하며, 여기서 9가 모두 뒤집힌 다음 새 위치에 대해 새 배열이 생성됩니다.

Answer 1

당신은 정확하지는 않지만 가깝습니다. 파이썬에서 배열 생성은 O (n) 이며, 최악의 경우 그 라인에 도달하려면 O (n) 인 전체 목록을 탐색해야합니다. 그래서 당신은 O (2n) 인 O (n + n)을 가지고 있습니다 (그러나 우리는 승수를 버리기 때문에 이것을 다시 O (n)로 분류 할 것입니다).

그러나 chepner가 말했듯이 여기서 반복이 더 나을 것입니다. 그리고 Ariel A에서 스윙 오프하려면 try except블록 place + 1이 인덱스 경계를 ​​벗어 났는지 확인하는 대신 사용할 수 있습니다.

if place + 1 >= len(digits)