随机快速排序最坏情况时间复杂度

Question

当出现以下两种情况之一时，最坏情况下普通快速排序的时间复杂度为 O(n^2)：

输入已按升序或降序排序
输入数组中的所有元素都相同

在上述两种情况下，PARTITION 算法会将数组分成两个子部分，一个包含 (n-1) 个元素，第二个包含 0 个元素

为了避免这种糟糕的情况，我们使用另一个版本的快速排序，即 Randomized Quick-Sort，其中选择一个随机元素作为主元。随机快速排序的预期 T.C 是 theta(nlogn).

我的问题是，对于什么 input/case，随机快速排序会导致 O(n^2) 的最坏时间复杂度？

Answer 1

如果输入包含完全相同的元素，则随机快速排序的运行时间为 O(n^2)。这是假设您使用与确定性版本中相同的 PARTITION 算法。分析相同

这是一个随机快速排序的实现，它计算执行的比较次数：

import random

def quicksort(A, lo, hi):
    if lo >= hi:
        return 0
    p, compares = partition(A, lo, hi)
    compares += quicksort(A, lo, p - 1)
    compares += quicksort(A, p + 1, hi)
    return compares

def partition(A, lo, hi):
    r = random.randrange(lo, hi+1)
    A[r], A[hi] = A[hi], A[r]
    pivot = A[hi]
    i = lo - 1
    compares = 0
    for j in xrange(lo, hi):
        compares += 1
        if A[j] < pivot:
            i = i + 1
            A[i], A[j] = A[j], A[i]
    compares += 1
    if A[hi] < A[i + 1]:
        A[i + 1], A[hi] = A[hi], A[i + 1]
    return i + 1, compares


for x in xrange(10, 510, 40):
    compares = quicksort([1] * x, 0, x-1)
    print x, compares

输出清楚地显示了 O(n^2) 运行时间：

随机快速排序最坏情况时间复杂度

Randomized Quick Sort worst case Time Complexity

sorting

algorithm

quicksort