資料結構›Ch1 演算法基礎
第 46 題/共 57 題
◀ DS 46/57
46. 分治法、遞迴複雜度分析
#DS-01-046易分治法遞迴複雜度分析
  1. (c) Assume a set GG whose elements are real numbers and the size of GG is equal to 2k2^k, where kk is a positive integer. We just want to find the maximum value and the minimum value in this set GG 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 T(N)T(N) to represent the number of comparisons when the set size is equal to NN. N=2kN = 2^k. Please find T(N)T(N) in terms of NN. (10%)

📄 成大110
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎
本章題號 · 41–57 / 57