考虑O((n-1)(n-3)(n-5).(n-n+1))跑步时间？

Question

我发现算法最坏的运行时间是O((n-1)(n-3)(n-5).(n+1))。这算不算O(n!)还是将其简化为更低的运行时间？

Answer 1

我们可以使用一些步骤为n!!提供n!和n的答案。首先，在n!!中，我们的条款是n!的一半。因此，我们可以想象采取n!和‘分割’(n/2)!。这是1*2*3*4...n / (1*2*3*4...n/2)在第一步。

然而，这是不完全正确的，因为我们要删除所有偶数，而不是所有小于n/2的数字！然而，好的是，现在我们可以把分母中的每一项都取下来，然后乘以2，得到2*4*6*8...(n-2)*n。如果我们将刚才使用的所有*2因子“除”出来，我们就会得到( n/2 )精确的(n/2)元素(因为这个序列中有n/2元素，并且所有元素都翻了一倍)。因此，n!! = n! / ((n/2)! * 2^(n/2))。因此，O(1*3*5*7...*(n-2)*n) = O(n!/((n/2)!2^(n/2))比n!更好(因为我们至少除以指数和较小的阶乘！)。希望这是有意义的

Answer 2

第一，当您谈到运行时间时，您应该使用T (n ) =(n-1)(n-3).(n+ 1)。其次，它不被认为是O(n!)，您可以为最坏情况下的时间复杂性提供更好的评估：

• 1 *2*3*n=n
• 2*4*8*n= 2^(n/2) *(n/2)

除法方程

1*3*5*n= n！/ (2^(n/2) * (n/2)!)

因此，最后的最坏情况复杂度是O(n！/ (2^(n/2) *(n/2)！)很明显，这个评估与O(n!)不同。