python - 为什么我的算法超时？

Question

这是问题(来自 Leetcode):

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 
Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

这是我的解决方案:

memo = {} 
def lis_calc(lower_bound, offset):
    if memo.get((lower_bound, offset), None):
        return memo[(lower_bound, offset)]
    if offset >= len(nums):
        return 0
    if nums[offset] > lower_bound:
        res = max(1 + lis_calc(nums[offset], offset + 1), lis_calc(lower_bound, offset + 1))
    else:
        res = lis_calc(lower_bound, offset + 1)

    memo[(lower_bound, offset)] = res 
    return memo[(lower_bound, offset)]

在最坏的情况下(列表已经按升序排序)，我们将有 NxN 个唯一的函数调用(每个参数成对有 N 个值)。然而，我的算法对于非常大的输入会超时，这表明我的算法没有 O(NxN) 的最坏情况时间成本。我在这里做错了什么吗？看起来像是 DP + memoization 的简单实现。超时的测试输入是 list(range(1,2501))

我通过lis_calc(float('-inf'), 0)调用该函数

Answer 1

您的算法可能不是二次的，而是指数的。

看看这段代码:

if nums[offset] > lower_bound:
    res = max(1 + lis_calc(nums[offset], offset + 1), lis_calc(lower_bound, offset + 1))

在最坏的情况下，每一步都会进行两次调用。在最坏的情况下，这两个调用中的每一个都会调用两次。这四个调用中的每一个调用都会进行两次调用，依此类推。

如果以下两件事之一为真，您的算法仍然可以是多项式:

• 如果这些新调用中至少有一半已缓存，或者
• 如果保证最坏的情况会在最坏的 log N 步内减少到下界情况(变成线性)。

但据我所知，这些都不是真的。因此，在最坏的情况下，您的算法需要 O(2**N) 步骤。这就是为什么它太慢的原因。

<小时/>

或者……也许这不是真的，也许它只是花费了二次时间和一个额外的常数因子，而 2500 就在他们期望你的代码能够舒适工作的边缘附近，而你只是没有完全通过？

每次将调用加倍时，您不会缓存其中的一半，但您应该缓存其中的一半 N-1。因此，如果一切顺利，您的总步数应该为 N * (N+1) + 1，但如果您稍有错误，则可能足以偏离 4 倍……虽然说实话，如果在他们测试的最大数字下常数因子 4 足以产生影响，我认为这并不是一个很好的测试。