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
我已經寫了“可能”快速排序演算法，因為我在這里注意到由于 for 回圈，磁區的時間復雜度為 O(n)，而且快速排序的復雜度似乎至少為 O(n)。問題是：整個代碼怎么可能有 O(nlogn) 的總時間復雜度。
uj5u.com熱心網友回復：
您的排序功能不是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。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/372450.html