資料結構›Ch1 演算法基礎第 46 題/共 57 題
46. 分治法、遞迴複雜度分析
#DS-01-046易分治法遞迴複雜度分析
- (c) Assume a set whose elements are real numbers and the size of is equal to , where is a positive integer. We just want to find the maximum value and the minimum value in this set and develop an algorithm in the following.
FindMaxMin(G)
If G contains only two numbers, then compare these two numbers,
set M to be the larger one, and set m to be the smaller one,
Else
Divide G into two subsets with equal size G1 and G2
Apply FindMaxMin(G1) to get M1 and m1
Apply FindMaxMin(G2) to get M2 and m2
M = max(M1, M2), m = min(m1, m2)
Return M, m
We use to represent the number of comparisons when the set size is equal to . . Please find in terms of . (10%)
📄 成大110
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎