algorithm - 漸化式の実行時間

Question

クイズでこれを持っていた：T（n）= 4T（sqrt（n））+ 5

置換を使用して簡略化し、F（k）= 4F（k / 2）+5を取得しました

マスター定理を使用して、私はそれがO（logn）であると推測しました。これは正確ですか？

Answer 1

定義

F(n) = T(2^n)

それから私たちはそれを持っています

F(n) = 4F(n/2) + 5

マスター定理により、私たちはそれを持っています

a = 4
b = 2
f(n) = 5 = O(1) = O(m^0), so c = 0
0 < 2 = log_2(4)

つまり、マスター定理のケース1です。ケース1では、

F(n) = Theta(n^2)

それで

T(2^n) = Theta(n^2)

したがって

T(n) = Theta(log(n^2)) = Theta(2logn) = Theta(log n)

そうです、あなたの答えは正しいようです。