python-3.x - 这两种解决 leetcode 873 的算法在时间和空间复杂度上有什么区别？

Question

我刚刚解决了https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/。目标是在严格递增的整数数组中找到最长的斐波那契子序列。

我需要一些帮助来确定我的解决方案与我从 leetcode 的解决方案部分得到的“最佳”解决方案之间的时间和空间复杂度差异。

1-我的算法：

class Solution:
    def lenLongestFibSubseq(self, A):
        dp = [collections.defaultdict(int) for i in range(len(A))]
        res = 2
        for j in range(len(A)):
            for i in range(j):
                prev = dp[i].get(A[j], 0)
                prev = 2 if not prev else prev+1
                dp[j][A[j]+A[i]] = prev
                res = max(res, prev)
        return res if res > 2 else 0

2-“最佳”算法：

class Solution:
    def lenLongestFibSubseq(self, A):
        dp = collections.defaultdict(int)
        s = set(A)
        for j in range(len(A)):
            for i in range(j):
                if A[j] - A[i] < A[i] and A[j] - A[i] in s:
                    dp[A[i], A[j]] = dp.get((A[j] - A[i], A[i]), 2) + 1
        return max(dp.values() or [0])

时间复杂度很简单——>它们都是O(n^2)

对于空间复杂性，我认为两者O(n^2)至少都是我的，因为对于每个索引，我维护一个大小等于index-1.

然而，“最佳”算法似乎也是O(n^2)空间，因为他正在为所有对缓存一个值[A[i], A[j]]。

我在这里是因为在线评委将我的解决方案评为慢 4 倍2000msvs500ms占用空间 345Mb倍15Mb。我可能遗漏了一些重要的东西，欢迎任何帮助。

标签： python-3.xalgorithmfibonaccisubsequence