主定理Case 2应用正确性验证请求：T(n)=T(n/2)+log n

你的推导是正确的，具体验证如下：

主定理Case2的适用条件 #

主定理第二种情况的核心要求是：当f(n) = Θ(n^{log_b a} * log^k n)（其中k ≥ 0）时，递归式的解为T(n) = Θ(n^{log_b a} * log^{k+1} n)。

对应你的递归式分析 #

• 给定递归式 T(n) = T(n/2) + log n，其中a=1，b=2，f(n)=log n
• 计算log_b a = log₂1 = 0，因此n^{log_b a} = n^0 = 1
• f(n)=log n可以表示为Θ(1 * log^1 n)，完全符合Case2的形式（这里k=1）
• 代入Case2的结论，得到T(n) = Θ(1 * log^{1+1} n) = Θ((log n)^2)，也就是你推导的O(logn²)（注：通常规范写法为O((logn)²)，避免和log(n²)混淆）

内容的提问来源于stack exchange，提问作者CBStudent