这个“最长的递减子序列”算法的时间复杂度是多少？

Question

我正在寻找数组中整数减少最长的子序列。这里我使用二进制搜索（我知道是O（logn）），所以我认为这个代码必须是O（nlogn）。我在这个特定输入上尝试了我的代码，它在0.02秒内运行。现在，我在网上搜索，我发现这个代码http://www.geekviewpoint.com/python/dynamic_programming/lds。作者说它需要O（n ^ 2），但在同样的输入上，它实际上需要0.01秒才能运行，这显然小于我的O（nlogn）算法。

def binary_search(arr, l, r, x):

    while r-l > 1:
        m = l + (r - l) // 2
        if arr[m] >= x:
            r = m
        else:
            l = m
    return r


def longest_decr_subseq_length(array, size):

    table = [0 for i in range(size + 1)]

    table[0] = array[n-1]
    length = 1

    for i in range(size - 1, -1, -1):
        if array[i] < table[0]:
            table[0] = array[i]
        elif array[i] > table[length - 1]:
            table[length] = array[i]
            length += 1
        else:
            table[binary_search(table, -1, length - 1, array[i])] = array[i]

    return length


lis = [38, 20, 15, 30, 90, 14, 6, 17]
n = len(lis)

print(longest_decr_subseq_length(lis, n))

那么，我的算法是O（n ^ 2）吗？或者那些是运行时间是正常的吗？如果问题看起来很愚蠢，我很抱歉，但我对算法很陌生并且仍然有些困惑

Answer 1

时间复杂度与执行时间不同。这意味着随着输入数据的增长，执行时间将如何增长。因此，即使时间复杂度较低，执行相同数量的数据也可能需要更长时间，但是当您以较低的时间复杂度增加输入数据算法的数量时，开始工作的速度会更快。至于你的算法的复杂性，你的计算似乎是正确的，它应该是O（nlogn）