大门|大门-CS-2017（第二组）|问题56

（A） θ（对数n） （B） θ（对数n） （C） θ（sqrt（n）） （D） θ（n） 答复: （B） 说明：

T(n) = 2T(√n) + 1

Let n = 2m

==> T(2m) = 2T(2m/2) + 1

Let S(m) = T(2m)
==> S(m/2) = T(2m/2)

Thus above equation will be : S(m) = 2S(m/2) + 1
Applying master’s theorem S(m) = m
Thus : T(n) = Θlog(n) (since n = 2m)

这个问题是重复的 https://www.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-17-2/ 这个问题的小测验