python - 为什么我们在估计算法的复杂度时只考虑输入的大小？

Question

为了论证，考虑以下(非常糟糕的)python 排序算法:

def so(ar):
    while True:
        le = len(ar)
        switch = False
        for y in range(le):
            if y+1 == le:
                break
            if ar[y] > ar[y+1]:
                ar[y],ar[y+1] = ar[y+1],ar[y]
                switch = True
        if switch == False:
            break
    return ar

我试图理解“算法的复杂性”的概念，但有一件事我不明白。

我看到了解释如何找到算法复杂度的帖子 here :

You add up how many machine instructions it will execute as a function of the size of its input, and then simplify the expression to the largest (when N is very large) term and can include any simplifying constant factor.

但是，问题是，我无法计算将要执行多少条机器指令 通过知道列表的长度。

考虑第一个例子:

li = [random.randint(1,5000) for x in range(3000)]
start = time.time()
so(li)
end = time.time() - start
print(end)

Output: 2.96921706199646

现在看第二个例子:

ok = [5000,43000,232] + [x for x in range(2997)]
start = time.time()
so(ok)
end = time.time() - start
print(end)

Output: 0.010689020156860352

我们可以看到，同一个排序算法，两个不同的列表，列表的长度是一样的，两个执行时间完全不同。

当人们谈论算法复杂性(大 O 表示法)时，他们通常假设决定算法复杂性的唯一变量是输入的大小，但很明显，在上面的示例中情况并非如此。决定排序速度的不仅是列表的大小，还有每个值在列表中的位置。

所以我的问题是，为什么我们在估计复杂性时只考虑输入的大小？ 而且，如果可能的话，您能告诉我上述算法的复杂度是多少吗？

Answer 1

你是对的，复杂性不仅仅取决于N。这就是为什么您会经常看到关于 average, worst and best cases 的指示。 .

Timsort在 Python 中使用是因为它平均为 (O n log n)，在最坏情况下仍然很快 (O(n log n))，在最佳情况下非常快(O(n)，当列表已经排序时)。

Quicksort也有 O(n log n) 的平均复杂度，但它的最坏情况是 O(n²)，当列表已经排序时。这个用例经常发生，所以实际上可能值得 shuffle the list在排序之前!