在看《算法导论》决策树求高度的时候用到斯特林公式对n!进行缩放,决策树的高度=Ω(nlgn)
斯特林公式(Stirling's approximation)是一条用来取n的阶乘的近似值的数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,所以斯特林公式十分好用,而且,即使在n很小的时候,斯特林公式的取值已经十分准确。
斯特林公式的形式:
或更精确的
或
想要看其疯狗一样的证明,详见百度百科!
在看《算法导论》决策树求高度的时候用到斯特林公式对n!进行缩放,决策树的高度=Ω(nlgn)
斯特林公式(Stirling's approximation)是一条用来取n的阶乘的近似值的数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,所以斯特林公式十分好用,而且,即使在n很小的时候,斯特林公式的取值已经十分准确。
斯特林公式的形式: