資料結構›Ch1 演算法基礎
第 54 題/共 57 題
◀ DS 54/57
54. Recurrence、Master Theorem、Divide and Conquer
#DS-01-054中RecurrenceMaster TheoremDivide and Conquer

Consider an analytical algorithm AA to take nn items as input set. When input size n≤4n \le 4, the process will terminate and return results, otherwise it will divide the input set into 4 roughly equal-size subsets; 2 of 4 subsets serve as samples and act as inputs to recursively apply AA twice; the results of the previous 2 outcomes (from the 2 recursive AA executions) each has n/4n/4 items; then we will use a procedure II to integrate the 2 outcomes, where II takes θ(m/4)\theta(\sqrt{m/4}) when inputs are 2 sets of size mm subsets. What about this algorithm are true?

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