代码之家 › 专栏 › 技术社区 › Belphegor

主定理:为什么t(n)=16t(n/4)+n!考虑(n)!

master-theorem

1

Belphegor · 技术社区 · 6 年前

我想知道为什么会有问题

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

被认为是

(n)!

我使用下面的主定理:

令人困惑的是,我的朋友说答案实际上是O(n!)而不是(n!)……所以我真的很困惑。

1 回复 | 直到 6 年前

1

0

kiner_shah Ahamed Raaseem 6 年前

CLRS定理:

在你的情况下, a = 16, b = 4, f(n) = n!

让我们计算一下 . 那将是 n^2

现在, n! 绝对大于和 N 2 ,那么我们将使用这个定理的第三种情况。

让 c = 0.5 . 这就产生了替代, 16 * (n / 4)! <= 0.5 * n!

让我们输入一个值 n 并检查:

如果 n = 100 , 16 * (100 / 4)! <= 0.5 * 100! 哪一个给予 16 * 25! <= 0.5 * 100! . 这个不等式是正确的,因为 100! 将远远大于 25! . 偶数乘以 16 不会超过 0.5 * 100! .

对于其他更大的值 N号 . 所以根据定理的复杂性应该是