函数的时间复杂度

Question

我有解决同一问题的两个版本。我真的很困惑如何计算时间复杂度（聊天 gpt 让我更加困惑哈哈）。

第一个版本：

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        elif (n == 1) or (n == 2):
            return 1
        else:
            memo = [0,1,1]
            for i in range(3,n+1):
                memo.append(memo[-1] + memo[-2] + memo[-3])
            print(memo)
            return memo[-1]

我认为这个版本的时间复杂度是 O(n) - 只是想确认这是否正确。

我的第二个版本是：

class Solution:
    def tribonacci(self, n: int) -> int:
        memo = {}

        def tribonacci_helper(n):
            if n == 0:
                return 0
            elif n == 1 or n == 2:
                return 1

            if n not in memo:
                memo[n] = tribonacci_helper(n-1) + tribonacci_helper(n-2) + tribonacci_helper(n-3)

            return memo[n]

        return tribonacci_helper(n)

我对这种（第二种）情况下的时间复杂度感到非常困惑。

您认为时间复杂度和空间复杂度哪个更好？

Chat gpt 说第二个版本的时间复杂度是 O(n)，但我认为是 O(3^n)，因为

tribonacci_helper

函数在其中调用了自己 3 次（但我可能是错的）。

Answer 1

两者都需要 θ(n²) 时间和空间。那是因为它们计算〜n个总和并且它们呈指数增长。例如，对于 n=1000，

sum(map(int.bit_length, memo))

（在第一个版本中）是 438943，而对于 n=2000，它是 1757031，大约是四倍（当您具有二次复杂度时，将 n 加倍）。

第二个版本并不像你想象的那么糟糕，因为

tribonacci_helper(n-2)

和

tribonacci_helper(n-3)

要么达到基本情况，要么达到已经记住的值，所以它们需要恒定的时间。

我想说第一个版本更好，因为它更简单并且不会遇到递归深度问题。但最好不要存储“所有”数字，而只跟踪最新的三个数字，因为这就是您继续所需的全部内容。这仍然需要 θ(n²) 时间，但只需要 θ(n) 空间。