大门|大门IT 2005 |问题51

设T（n）是由递归定义的函数

T（n）=2T（n/2）+√n换n≥ 2和 T（1）=1

以下哪项陈述是正确的？

（A） T（n）=θ（对数n） （B） T（n）=θ(√n） （C） T（n）=θ（n） （D） T（n）=θ（n对数n） 答复: （C） 说明： N ^{（日志） _B （a）} n是n^（1-.5）=O（sqrt n） 然后应用主方法的情况1，我们得到T（n）=Θ（n）

请参考 https://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/ 更多细节。 这个问题的小测验