python 时间复杂度快速排序算法

Question

def partition(A, l, r):
    p = A[l]
    stack = A[l]
    A[l] = A[r]
    A[r] = stack
    s = l

    for i in range(l, r):

        if A[i] <= p:

            stack2 = A[i]
            A[i] = A[s]
            A[s] = stack2
            s += 1

    stack3 = A[s]
    A[s] = A[r]
    A[r] = stack3

    return s

def quicksort(A, l, r):

    if l < r:

        q = partition(A, l, r)
        quicksort(A, l, q - 1)
        quicksort(A, q + 1, r)
    return A

我写了“可能”的快速排序算法，因为我在这里注意到分区的时间复杂度是 O(n) 因为 for 循环，而且快速排序的复杂度似乎至少是 O(n ).问题：整个代码的总时间复杂度如何可能为 O(nlogn)。

Answer 1

您的排序功能不是 O(nlogn)。在最坏的情况下，您正在进行 O(n) 次递归调用。

作为一个简单的测试：

def test(n):
    nums = list(reversed(range(n)))
    return sum(quicksort(nums,0,n-1))

然后，例如，test(1100) 触发器：

RecursionError: maximum recursion depth exceeded in comparison

如果您只调用 partition log(n) 次就不会发生这种情况。

另一方面，

import random

def test2(n):
    nums = list(range(n))
    random.shuffle(nums)
    return sum(quicksort(nums,0,n-1))

甚至对于像 test2(100000) 这样的调用也能很好地工作，所以你确实有 平均情况 O(nlogn) 复杂性。这在数值上很容易证实，但很难证明。见 https://en.wikipedia.org/wiki/Quicksort 证明。

Answer 2

你每级划分 2，直到你得到单独的元素。划分和比较什么使时间复杂。您在每个级别进行 n 次比较，您将进行 log2(n) 次分区。

在最坏的情况下，您的数组已经排序，您将进行 n 次分区，并且仍然在每个级别进行 n 次比较。

python 时间复杂度快速排序算法

python time complexity quick sort algorithm

python

python-3.x

algorithm

time-complexity

quicksort