算法导论第九章习题解答

def GETVALUE(a): if a[1] == None: return a[0] return GETVALUE(a[0]) def PARTITION_BYVALUE(A, p, r, value): flag = p i = p for j in range(p, r+1): print(A[j], GETVALUE(A[j]), GETVALUE(value)) if GETVALUE(A[j]) <= GETVALUE(value): temp = A[i] A[i] = A[j] A[j] = temp if GETVALUE(A[i]) == GETVALUE(value): flag = i i = i + 1 if i > flag: temp = A[i-1] A[i-1] = A[flag] A[flag] = temp return i-1 def INSERTION_SORT(A): for j in range(1, len(A)): key = A[j] i = j - 1 while i >= 0 and GETVALUE(A[i]) > GETVALUE(key): A[i + 1] = A[i] i = i - 1 A[i + 1] = key def SELECT(A, p, r, i): if p == r: return A[p] B = [] midarray = [] for j in range(p, r+1, 5): if j+5 > r: B.append(A[j:r+1]) else: B.append(A[j:j+5]) INSERTION_SORT(B[len(B)-1]) midarray.append(B[len(B)-1][len(B[len(B)-1])//2]) mid = SELECT(midarray, 0, len(midarray)-1, len(midarray)//2) q = PARTITION_BYVALUE(A, p, r, mid) assert(A[q] == mid) k = q-p+1 if i == k: return A[q] elif i < k: return SELECT(A, p, q-1, i) else: return SELECT(A, q+1, r, i-k) def SMALL_SELECT(A, i): """ a) 这题怎么处理我想不出来，只能根据给定的公式逆推出来 Ui 寻找第i小的元素； T 直接调用select寻找第k小的元素，k不一定为i 1.若 i>= n/2 直接调用select 2.else 有floor(n/2) + Ui(ceil(n/2)) + T(2i) 执行步骤， 3.Ui为递归，递归的规模减少一半，故floor(n/2)(根据提示)应该是将原数组两两比较大小再拆分， 保证了前一半的元素小于后一半的元素，再调用SMALL_SELECT选取第i小元素， 4.T(2i) 在2i个元素中寻找某第k个顺序统计量，问题在于如何确定最后第k个统计量与原数组第i个统计量的关系， 第一步保证了Ui的元素每次都是从0开始到某个小于n/2元素的顺序取值 故T(2i)次比较应该是从0到2i个元素的比较，且保证输入数组的第i个元素落入0到2i的元素区间 5.参考9.1_1,使得输入数组的第i个元素必然落在小于等于i的元素或与i比较过的元素上,即记录比较过的元素 """ n = len(A)//2 if len(A)%2 != 0: n = n+1 if i >= n: ith = SELECT(A, 0, len(A)-1, i) return ith B = [] for j in range(0, n): if j + n >= len(A): B.append(A[j]) elif GETVALUE(A[j]) < GETVALUE(A[j+n]): B.append((A[j], A[j + n])) else: B.append((A[j + n], A[j])) iths = SMALL_SELECT(B, i) C = [] for s in B: if GETVALUE(s) <= GETVALUE(iths): C.append(s[0]) C.append(s[1]) if len(C) > 0: ith = SELECT(C, 0, len(C)-1, i) return ith else: return iths def SMALL_ORDER_SELECT(A, i): B = [] for a in A: B.append((a, None)) v = SMALL_SELECT(B, i) #v = SELECT(B, 0, len(B)-1, i) return GETVALUE(v) """ b) 用代入法，设结果成立，然后将结果代入到原式中化简 """ """ c) i为常数时，可令T(2i) = O(1), 且 lgi = O(1) """ """ d) k >= 2 i=n/k, i<n/2 将i代入题 b)的结论中化简得 """ if __name__ == "__main__": array = [1,22,7,49,21,75,92,25,63,49,28,64,12,9] print(SMALL_ORDER_SELECT(array, 4))