python - 我的代码的运行时复杂度是 O(a+b) 吗？

Question

我刚刚在 LeetCode 上解决了这个问题。它非常简单，但我不确定代码的运行时复杂性。谁能给我解释一下。

def addBinary(self, a: str, b: str) -> str:
        carry = 0
        result = ''

        a = list(a)
        b = list(b)

        while a or b or carry:
            if a:
                carry += int(a.pop())
            if b:
                carry += int(b.pop())

            result += str(carry %2)
            carry //= 2

        return result[::-1]

Answer 1

你的循环将一直运行直到 a 或 b 中没有任何内容，并且进位为 0。每次迭代时，都会将 a 和 b 中的条目数减少一个。因此，总迭代次数为 max(len(a),len(b)) +x其中 x如果最后进位还有东西，则为 1，否则为 0 因为 x 基本上受常数(常数 1)的限制，所以对于渐近部分可以忽略它。

请注意 (len(a)+len(b))/2<=max(len(a),len(b))<=len(a)+len(b)所以

max(len(a),len(b))+1 是 O(len(a)+ len(b))

并且 len(a)+len(b) 是 O( max(len(a),len(b)))