runtime-error - 谁能帮我找到大的 theta 运行时复杂度

Question

我对 Big Theta ( Θ ) 运行时复杂度的概念不熟悉，

我有以下递归关系要分析，

T(n) = 2T(n/3) + 5n ² 我得到Θ( ² )

T(n) = T(n/4) + n ⁴ 我得到Θ(n ⁴ )

请验证我的回答。

Answer 1

你的答案是正确的。您可以通过应用主定理来解决这些问题。

链接是主定理，

http://en.wikipedia.org/wiki/Master_theorem#Generic_form

如果T(n) = a T(n/b) + f(n)其中 a >= 1 且 b > 1

我们需要考虑主定理的案例3，

案例 3：如果f(n) = Θ(n ^c ) 其中c > log _b a

那么T(n) = Θ(n ^c )

第一次复发

T(n) = 2T(n/3) + 5n ²

a = 2, b = 3 和 f(n) = 5 n ²

其中，f(n) = Θ(n ^c )，其中 c = 2。

现在 c > log _b a since 2 > log ₃ 2。

因此，您提到的T(n) = Θ(n ^{2 )。}

第二次复发

T(n) = T(n/4) + n ⁴

a = 1, b = 4 和 f(n) = n ⁴

其中，f(n) = Θ(n ^c )，其中 c = 4。

现在 c > log _b a since 4 > log ₄ 1。

因此，您提到的T(n) = Θ(n ^{4 )。}

Answer 2

这些都是正确的。因为每个递归方程的第二项比第一项高得多，所以它将支配第一项（用外行的话来说）。