大门| 2008年大门|问题42

当n=2时 ^2k 为了一些k≥ 0，递归关系

T（n）=√（2） T（n/2）+√n、 T（1）=1

评估结果如下： （A） √（n） （日志n+1） （B） √（n） （日志n） （C） √（n） 日志√（n） （D） n日志√（n） 答复: （A） 说明： 请注意，问题是关于精确解的。 主定理 以 式表示法 所以我们不能在这里应用主定理。我们可以用简单的展开或递归树方法来解决这个问题。

T(n) = √(2) T(n/2) + √n
     = √(2) [√(2) T(n/4) + √(n/2) ] + √n
     = 2 T(n/4) + √2 √(n/2) +√n
     = 2[ √2 T(n/8) + √(n/4) ]+√2 √(n/2)+√n
     = √(2^3) T(n/8)+ 2 √(n/4) + √2 √(n/2) +√n
     = √(2^3) T(n/8)+√n +√n +√n
     = √(2^3) T(n/(2^3))+3√n
     .............................................
     = √(2^k) T(n/(2^k))+k√n
     = √(2^logn) + logn √n
     = √n + logn √n
     = √n(logn +1)

替代解决方案： 这个问题可以很容易地用替换法解决。看： T（1）=1；鉴于 现在在给定的递推关系中使用n=2，该递推关系给出2*（1.414）（因为根在2上的值是1.414） 现在通过查看选项，使用满足选项A的n=2。

这个问题的小测验