我正在研究演算法的復雜性，我試圖弄清楚這個在我腦海中運行的問題 - O(n!) 比 O(2^n) 快還是相反？
uj5u.com熱心網友回復：
O(2^n)是2 * 2 * 2 * ...哪里O(n!)的1 * 2 * 3 * 4 * ...
O(n!)會很快變得更大 - 所以O(2^n)更快。
例如：2^10 = 1024和10! = 3628800
uj5u.com熱心網友回復：
你可以嘗試用作業斯特靈公式為n!
https://en.wikipedia.org/wiki/Stirling's_approximation
n! = (n / e)^n * sqrt(2 * Pi * n) * (1 o(n))
現在，讓我們比較
O(n!) <=> O(2^n)
為了找出正確的字母<，=或者>讓我們計算極限
lim (n! / 2^n) =
n -> inf
lim (n / e)^n * sqrt(2 * pi * n) / 2^n >=
n -> inf
lim n^n / (2 * e)^n >= // when n > 4 * e
n -> inf
lim (4 * e)^n / (2 * e)^n =
n -> inf
lim 2^n = inf
n -> inf
所以
lim (n! / 2^n) = inf
n -> inf
意思就是 O(n!) > O(2^)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/354726.html
上一篇：WPF設計器不會自動加載