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

Question

我在寻找数组中整数的最长递减子序列。这里我使用的是二进制搜索(我知道是O(logn))，所以我认为这段代码必须是O(nlogn)。我在这个特定的输入上尝试了我的代码，它在0.02秒内运行。现在，我在网上搜索，我发现了这个代码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)。