0

我是第一次研究这个算法。CLRS (15-4.6) 要求编写一个算法以在 O(n lg n) 时间内运行。我想出的算法似乎在 O(n) 中运行。我想我一定是误解了一些东西，因为即使是维基百科也说它应该花费 O(n lg n) 时间。（https://en.wikipedia.org/wiki/Longest_increasing_subsequence）
有人能告诉我为什么这个算法（在 Python 中）不能正常工作或者不是 O(n) 或者不能回答这个问题吗？

"""Attempts to find maximal ordered subsequence in linear time."""

def subseq(n):
    """Assumes the elements of n are unique"""
    if len(n) == 1:
        return n[:]
    first = [n[0]]
    second = []
    for i in range(1,len(n)):
        if n[i] > first[-1]:
            second = first[:]
            first.append(n[i])
        elif not second or n[i] > second[-1]:
            first = second[:]
            first.append(n[i])
    return first

print subseq([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])
4

1 回答 1

0

我将把一些调试留给你，但以下不会使用你的算法产生最大长度的子字符串。我只是在您的示例中添加了一些数字，因此它应该[0, 4, 6, 9, 11, 15]再次生成，但没有：

>>> print(subseq([0, 12,12,15,14 ,8, 4, 12, 14, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]))
[0, 12, 13, 15]
于 2016-10-10T06:29:15.113 回答