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 に答える