CLRS递归式T(n)=T(⌈n/2⌉)+1证明O(lg n)的推理错误排查

核心错误定位 #

你的推理中最关键的错误是错误假设了⌈f(n)/2⌉*2 = f(n)，这个等式仅在f(n)为偶数时成立；当f(n)是奇数时，⌈f(n)/2⌉ = (f(n)+1)/2，此时⌈f(n)/2⌉*2 = f(n)+1 ≠ f(n)。对向上取整运算性质的误解，直接导致后续推导全部偏离正确方向。

正确的换元法推导思路 #

无需引入额外的f(n)，直接对原递归式结合数学归纳法推导：

• 归纳基础：当n=1时，T(1)为常数，取足够大的常数d，可满足T(1) ≤ c*lg1 + d = d。
• 归纳假设：假设对所有x < n，T(x) ≤ c*lgx + d成立。
• 归纳步骤：
  1. 对n≥2，T(n) = T(⌈n/2⌉) + 1 ≤ c*lg(⌈n/2⌉) + d + 1
  2. 利用向上取整性质：⌈n/2⌉ ≤ (n+1)/2，因此lg(⌈n/2⌉) ≤ lg((n+1)/2) = lg(n+1) - 1
  3. 代入得：T(n) ≤ c*(lg(n+1)-1) + d + 1 = c*lg(n+1) + (d + 1 - c)
  4. 要使T(n) ≤ clg n + d，只需clg(n+1) + (d +1 -c) ≤ clg n + d，化简得：clg(1+1/n) ≤ c-1
  5. 当n≥2时，lg(1+1/n) ≤ lg(3/2)≈0.585，取c≥2，左边≤2*0.585≈1.17 < 2-1=1，不等式成立。

原推导的错误步骤拆解 #

在你的推导流程中：

• 从f(n)/⌈f(n)/2⌉ ≥ exp(c)到用⌈f(n)/2⌉*2 = f(n)替换的环节完全错误，比如f(n)=3时，⌈3/2⌉=2，2*2=4≠3，此时f(n)/⌈f(n)/2⌉=3/2=1.5，而非你假设的2。
• 基于这个错误等式的后续推导自然得出了不合理的结论，本质是对向上取整运算的核心性质理解偏差。

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