第8章 中位數和順序統計量
- 中位數：其所屬集合的中點元素，
- 當元素個數n為奇數時，中位數唯一， i = ( n + 1 ) / 2 i=(n+1)/2 i=(n+1)/2
- 當元素個數n為偶數時，存在兩個中位數，分別為 i = n / 2 i=n/2 i=n/2和 i = n / 2 + 1 i=n/2+1 i=n/2+1
- 若不考慮n的奇偶性，中位數總是出現在== i = ? ( n + 1 ) / 2 ? i=\lfloor (n+1)/2\rfloor i=?(n+1)/2?和 i = ? ( n + 1 ) / 2 ? i=\lceil (n+1)/2\rceil i=?(n+1)/2?==處，
8.1 最小值和最大值
-
尋找最小值：依次遍歷集合中的每個元素，并記錄下當前最小元素，
-
偽代碼：MINIMUM(A)
min = A[0] for i = 2 to A.length if min > A[i] min = A[i] return min -
python代碼：
def minimum(A): min = A[0] for i in range(1, len(A)): if min > A[i]: min = A[i] return min A = [10, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1] print(minimum(A))
8.2 期望為線性時間的選擇演算法
-
偽代碼：RANDOMIZED-SELECT(A, p, r, i)
if p == r return A(p) q = RANDOMIZED-PATITION(A, p, r) k = q - p + 1 if i == k return A[q] else if i < k return RANDOMIZED-SELECT(A, p, q-1, i) else return RANDOMIZED-SELECT(A, q+1, r, i-k) -
最壞情況運行時間： θ ( n 2 ) \theta(n^2) θ(n2)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/262205.html
標籤：python
下一篇：新手 ，請教C++一道作業題