首页 > 代码库 > Selection in expected linear time O(n)
Selection in expected linear time O(n)
Selection in expected linear time
The general selection problem appears more difficult than the simple problem of finding a minimum. Yet, surprisingly, the asymptotic running time for both problems is the same: theta(n).
In this section, we present a divide-and-conquer algorithm for the selection problem. The algorithm R ANDOMIZED-SELECT is modeled after the quicksort algorithm of Chapter 7. As in quicksort, we partition the input array recursively. But unlike quicksort, which recursively processes both sides of the partition, R ANDOMIZED -S ELECT works on only one side of the partition. This difference shows up in the analysis: whereas quicksort has an expected running time of theta{n*lg(n)}, the expected running time of RANDOMIZED-S ELECT is O(n), assuming that the elements are distinct.
下面是random_select()的实现:
返回在输入数据中,第i大的数据,时间复杂度是O(n)
""" Code writer : EOF Code date : 2015.01.15 Code file : random_select.py e-mail : jasonleaster@gmail.com Code description : Here is a implementation for random-select in Python. Function @random_select(A, p, r, i) will return the i-th element from the @A which's range is @p to @r. """ import random def partition(A, p, r) : x = A[r] i = p-1 for j in range(p, r) : if A[j] <= x : i += 1 # swap A[i] and A[j] A[i], A[j] = A[j], A[i] A[i+1], A[r] = A[r], A[i+1] return i+1 def random_partition(A, p, r) : i = random.randint(p,r) A[r], A[i] = A[i], A[r] return partition(A, p, r) def random_select(A, p, r, i) : if p == r : return A[p] q = random_partition(A, p ,r) k = q - p + 1 if i == k : return A[q] elif i < k : return random_select(A, p, q-1, i) else : return random_select(A, q+1, r, i-k) #-------------------testing code--------------------------- A = [13,19,9,5,12,8,7,4,21,2,6,11] print "Before sorting A= " , A x = random_select(A,0,len(A)-1, 5) print "After sorting A= " , sorted(A), x
Selection in expected linear time O(n)