Каковы различия во временной и пространственной сложности между этими двумя алгоритмами, которые решают Leetcode 873? - PullRequest
Новая
       35

Каковы различия во временной и пространственной сложности между этими двумя алгоритмами, которые решают Leetcode 873?

0 голосов
/ 06 июля 2019

Я только что решил 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), по крайней мере, мое точно, так как для каждого индекса я поддерживаю dict, размер которого равен index-1.

Однако «оптимальный» алгоритм выглядит так, будто он тоже O(n^2) пробел, поскольку он кэширует одно значение для всех пар [A[i], A[j]].

Я здесь, потому что он-лайн судья оценивает мое решение как в 4 раза медленнее 2000ms против 500ms и в 3 раза как занимающее место 45Mb против 15Mb. Я мог бы пропустить что-то большое, любая помощь приветствуется.

...