algorithm - 定数を持つマスター定理

Question

この式はマスター定理のケース 2 ですか?

T(n) = 2 * T(n/2) + 3

a = 2; b = 2; (f(n) = 3^1) ?

この場合、logba = 1 かつ c = 1 はマスター定理ケース 2 ですか? または、定数 3 を無視する必要があります。

Answer 1

これはケース 1の式です。

log_b(a) = 1
f(n) = 3,
3 is in O(1)=O(n^0) -> c = 0 < 1 = log_b(a)

したがって、式は次のとおりですTheta(n^(log_b(a)) = Theta(n)

f(n)=3ケース 2 はにある必要があるため、これはケース 2 ではありませんTheta(n^(log_b(a)) = Theta(n)が、f(n)=3含まれていません。Theta(n)