algorithm - 以下表达式的时间复杂度是多少?

标签 algorithm time-complexity

T(n) = 16T(n/4) + n!

我知道可以用Master theorem解决,但是我不知道怎么处理 f(n) = n!

最佳答案

这是 Master Theorem 的案例三。

因为 T(n) = 16T(n/4) + n!

这里 f(n) = n!。

a = 16 和 b = 4,所以 logb a = log4 16 = 2。

主定理指出复杂度 T(n) = Θ(f(n)) 如果 c > logb a 其中 f(n) ∈ Ω(nc) 。 由于 f(n) = n! > nc 对于 n > n0 的某个值,语句 f(n) ∈ Ω (nc) 为真。因此声明 c > logb a =2 也成立。因此,根据 Thoerem 大师的第三个案例,复杂性 T(n) = Θ(f(n)) = Θ(n!)

关于algorithm - 以下表达式的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40415949/

相关文章:

c++ - 如何确定数据点的两个分区(聚类)是否相同?

algorithm - 在 Kruskal 算法中使用 union-find 是否真的会影响最坏情况下的运行时间?

c++ - O(log n) 索引更新和搜索

algorithm - 是 log (n!) 的下界也是 nlogn

algorithm - 我的拼写检查器无法正确比较单词

c - 带两个可用的加权间隔调度 "workers"

python - 定义特定于条件的变量是好的做法吗

javascript - 这是解决数组分区问题的正确方法吗?

javascript - array.prototype.includes 与 set.prototype.has 的时间复杂度

algorithm - 具有可变时间复杂度的嵌套 for 循环