big-o - 我们如何以最简单的方式用 Theta 和 Big Oh 表示法编写 nCr？

Question

我们如何以最简单的方式在 Theta 和 Big Oh Notation 中编写nCr ？

例如对于小的 rs，我们有：
nC2 = n * (n-1) / 2 = Θ(n ² ) = O(n ² )
nC3 = n * (n-1) * (n-2) / 6 = Θ (n ³ ) = O(n ³ )

对于任意的n和r，我们有：nCr = Θ(n! / (r! * (nr)!))
是否可以用更简单的方式编写nCr？
例如，我们可以写nCr = Θ(n! / max(n,nr)!)或其他任何东西，为什么？

标签： big-ocombinatorics

Answer 1

如果r是一个你知道的常数，只需简化nCr为Θ(n^r).

如果r是您要描述的其他参数，只需编写Θ(nCr). 这正是您为图形算法所做的事情，您在其中写入Θ(n*m)节n点数和m边数，即使您可以将其限制在O(n^3).

如果r可以是任何东西并且您无法控制它，请使用最坏的情况r = n/2并尝试使用斯特林近似来简化它。