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

Question

null

Answer 1

如果输入包含所有相同的元素，则randomized quick-sort的运行时为O(n^2)。这是假设您使用与确定性版本相同的分区算法。分析结果是相同的。

下面是随机quicksort的一个实现，它计算执行的比较数：

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)个运行时：

10 54
50 1274
90 4094
130 8514
170 14534
210 22154
250 31374
290 42194
330 54614
370 68634
410 84254
450 101474
490 120294