資料結構›Ch1 演算法基礎
第 37 題/共 57 題
◀ DS 37/57
37. Recurrence、Θ 分析
#DS-01-037中RecurrenceΘ 分析

Given a set SS of size n=22mn = 2^{2^m}, where m∈Z+m \in \mathbb{Z}^+, 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 T(n)T(n) represent the time required to use this algorithm to cluster and label a set of size nn. Provide an asymptotic tight bound (Θ\Theta) for T(n)T(n), assuming that T(n)T(n) is a constant for sufficiently small nn.

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