乘以系数的阶乘的大 Theta
Big Theta of Factorial Multiplied by a Coefficient
对于运行时间为(cn)的函数！其中 c 是系数 >= 0 且 c != n，运行 的紧界是 Θ(n!) 还是 Θ((cn)!)？现在，我相信它会是 Θ((cn)!) 因为它们会相差一个系数 >= n 因为 cn != n.
谢谢！
编辑：一个更具体的例子来阐明我的问题：
将 (7n)!, (5n/16)!和 n！都是 Θ(n!)?
你可以用Stirling's approximation得到if c>1 then (cn)！渐近大于 pow(c,n)*n!，它不是 O(n!)，因为商发散。作为一种更基本的方法，考虑 c=2 的这个例子：(2n)!=(2n)(2n-1)...(n+1)n!>n!n!和 (n!n!)/n!=n!发散，所以 (2n)!不是 O(n!).
Will (7n)!, (5n/16)! and n! all be Θ(n!)?
我想你的问题有两个答案。
较短的一篇是纯理论的。在这 3 个中，只有 n! 位于 Θ(n!) 的 class 中。第二个在于 O(n!)（注意 big-O 而不是 big-Theta）并且 (7n)! 比 Θ(n!) 慢，它在于 Θ((7n)!)
还有一个更长但更实用的答案。为了做到这一点，我们首先需要了解整个 big-O 和 big-Theta 业务的重要之处是什么？
事实是，对于许多实际任务，有许多算法，但并非所有算法都具有相同甚至相似的效率。所以实际问题是：我们能否以一种易于理解和比较的方式以某种方式捕捉到这种性能差异？而这正是 big-O/big-Theta 试图解决的问题。这种方法背后的想法是，如果我们用一些复杂的真实公式来查看某些算法的确切时间，只有 1 项比所有其他项增长得更快，因此随着问题变大，它会支配时间。因此，让我们将这个大公式压缩为那个主导项。然后我们可以比较这些术语，如果它们不同，我们可以很容易地说出哪个算法更好（7*n^2 显然比 2*n^3 好）。
另一个想法是，术语 "operation" 通常在人们通常认为的算法级别上定义不那么明确。哪个 "operation" 实际上映射到单个 CPU 指令，哪个映射到几个取决于许多因素，例如特定硬件。此外，指令本身可能需要不同的时间来执行。此外，有时算法的工作时间主要由内存访问而不是 CPU 指令决定，并且这些组件不容易添加。这个故事的士气是，如果两种算法仅在标量系数上不同，那么您不能仅在理论上比较这些算法。您需要比较某些特定环境中的某些实现。这就是为什么算法复杂性度量通常归结为 O(n^k) 之类的原因，其中 k 是一个常数。
还有一个考虑因素：实用性。如果算法是某种多项式，[=22=20=] 和 a=4 之间的 实用 差异很大=].但是如果是O(2^(n^a))这样的东西，那么a和a>1并没有太大区别。这是因为 2^n 增长得足够快，以至于它对于几乎任何现实的 n 都是不切实际的，而不管 a。所以实际上，将所有这些算法放入一个 "exponential algorithms" 桶中并说它们都是不切实际的，即使它们之间存在巨大差异，这通常是足够好的近似值。这就是一些非常规的数学符号如 2^O(n) 的来源。
从最后一个实用的角度来看，Θ(n!) 和 Θ((7n)!) 之间的区别也很小：两者都是完全不切实际的，因为它们甚至都超出了 2^O(n) 的指数范围（见 Stirling's formula 这表明 n! 比 (n/e)^n 增长得快一点）。因此，将所有此类算法放在另一个 "factorial complexity" 桶中并将它们也标记为不切实际是有意义的。
对于运行时间为(cn)的函数！其中 c 是系数 >= 0 且 c != n，运行 的紧界是 Θ(n!) 还是 Θ((cn)!)？现在，我相信它会是 Θ((cn)!) 因为它们会相差一个系数 >= n 因为 cn != n.
谢谢！
编辑：一个更具体的例子来阐明我的问题：
将 (7n)!, (5n/16)!和 n！都是 Θ(n!)?
你可以用Stirling's approximation得到if c>1 then (cn)！渐近大于 pow(c,n)*n!，它不是 O(n!)，因为商发散。作为一种更基本的方法，考虑 c=2 的这个例子：(2n)!=(2n)(2n-1)...(n+1)n!>n!n!和 (n!n!)/n!=n!发散，所以 (2n)!不是 O(n!).
Will (7n)!, (5n/16)! and n! all be Θ(n!)?
我想你的问题有两个答案。
较短的一篇是纯理论的。在这 3 个中，只有 n! 位于 Θ(n!) 的 class 中。第二个在于 O(n!)（注意 big-O 而不是 big-Theta）并且 (7n)! 比 Θ(n!) 慢，它在于 Θ((7n)!)
还有一个更长但更实用的答案。为了做到这一点，我们首先需要了解整个 big-O 和 big-Theta 业务的重要之处是什么？
事实是，对于许多实际任务，有许多算法，但并非所有算法都具有相同甚至相似的效率。所以实际问题是：我们能否以一种易于理解和比较的方式以某种方式捕捉到这种性能差异？而这正是 big-O/big-Theta 试图解决的问题。这种方法背后的想法是，如果我们用一些复杂的真实公式来查看某些算法的确切时间，只有 1 项比所有其他项增长得更快，因此随着问题变大，它会支配时间。因此，让我们将这个大公式压缩为那个主导项。然后我们可以比较这些术语，如果它们不同，我们可以很容易地说出哪个算法更好（7*n^2 显然比 2*n^3 好）。
另一个想法是，术语 "operation" 通常在人们通常认为的算法级别上定义不那么明确。哪个 "operation" 实际上映射到单个 CPU 指令，哪个映射到几个取决于许多因素，例如特定硬件。此外，指令本身可能需要不同的时间来执行。此外，有时算法的工作时间主要由内存访问而不是 CPU 指令决定，并且这些组件不容易添加。这个故事的士气是，如果两种算法仅在标量系数上不同，那么您不能仅在理论上比较这些算法。您需要比较某些特定环境中的某些实现。这就是为什么算法复杂性度量通常归结为 O(n^k) 之类的原因，其中 k 是一个常数。
还有一个考虑因素：实用性。如果算法是某种多项式，[=22=20=] 和 a=4 之间的 实用 差异很大=].但是如果是O(2^(n^a))这样的东西，那么a和a>1并没有太大区别。这是因为 2^n 增长得足够快，以至于它对于几乎任何现实的 n 都是不切实际的，而不管 a。所以实际上，将所有这些算法放入一个 "exponential algorithms" 桶中并说它们都是不切实际的，即使它们之间存在巨大差异，这通常是足够好的近似值。这就是一些非常规的数学符号如 2^O(n) 的来源。
从最后一个实用的角度来看，Θ(n!) 和 Θ((7n)!) 之间的区别也很小：两者都是完全不切实际的，因为它们甚至都超出了 2^O(n) 的指数范围（见 Stirling's formula 这表明 n! 比 (n/e)^n 增长得快一点）。因此，将所有此类算法放在另一个 "factorial complexity" 桶中并将它们也标记为不切实际是有意义的。