算法的复杂度是多少:T (n) = 3 * T (n ÷ b) + n² + 1？ 问一个问题
一个
你能帮我知道复杂度是多少:T (n) = 3 * T (n ÷ b) + n² + 1。当 n> 1 时？。
自从我必须做一个学校演示来解决这个问题以来，我一直试图了解一些计算算法复杂度的主要方法，但我一直没能很好地解决它。如果你能给我建议，我会非常重视。
谢谢!
最佳答案
如果b等于1，master的临界系数未定义，不满足正则性条件。在这种情况下，T(n) 根本无法明确定义，也没有任何合理的解决方案。
如果b等于2，master定理的临界系数为log_2(3)，n^log_2(3) = O(n^2)...同样，因为此时T(n)满足正则性，Master定理告诉我们这里的复杂度是 O(n^2)。
事实上，对于任何大于 2 的 b，上述分析也适用:对于大于 1 的整数 b，log_b(3) 总是小于 2。对于任何这样的选择，都会满足规律性，所以我们总是在Master 定理的情况 3 并有 T(n) = O(n^2)。
关于algorithm - 算法的复杂度是多少 : T (n) = 3 * T (n ÷ b) + n² + 1?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55214366/