高手定理：为什么T(n)=16T(n/4)+n！考虑 Θ(n!)
Master Theorem: Why is T(n)=16T(n/4)+n! considered Θ(n!)
我在尝试理解为什么
时遇到了一些问题
T(n)=16T(n/4)+n!
被考虑
Θ(n!)
我在这里使用下面的主定理：
https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/
这里比较迷惑的地方是我的朋友说答案实际上是O(n!)而不是Θ(n!)...所以我真的很迷惑
来自 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 的其他较大值也是如此。所以根据定理的复杂度应该是
我在尝试理解为什么
时遇到了一些问题T(n)=16T(n/4)+n!
被考虑
Θ(n!)
我在这里使用下面的主定理：
https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/
这里比较迷惑的地方是我的朋友说答案实际上是O(n!)而不是Θ(n!)...所以我真的很迷惑
来自 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 的其他较大值也是如此。所以根据定理的复杂度应该是