資料結構›Ch1 演算法基礎第 37 題/共 57 題
37. Recurrence、Θ 分析
#DS-01-037中RecurrenceΘ 分析
Given a set of size , where , we use the following algorithm to perform clustering and labeling:
F(S)
1 If |S| == 2 then return;
2 Apply a clustering algorithm with a time complexity of Θ(lg n) to divide the set S
into three clusters, S1, S2, and S3, and label them where |S| = n, |S1| = |S2| = √n,
and |S3| = n − 2√n.
3 Call F(S1)
4 Call F(S2)
Let represent the time required to use this algorithm to cluster and label a set of size . Provide an asymptotic tight bound () for , assuming that is a constant for sufficiently small .
📄 成大114
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎