作者arrenwu (不是绵芽的错)
看板Math
标题Re: [其他] 关於时间复杂度（big O）的排序
时间Tue Dec 14 10:44:24 2021
※ 引述《MMaze (Maze)》之铭言：
:
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 103.232.136.184 (台湾)
: ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1639204484.A.AC6.html
: 推 bigbigloser : 如果是以2为底，2^(log(N))就是N 12/11 15:43
: → bigbigloser : 然後2^(2^N)比N!大才对(一项一项比较) 12/11 15:46
: → MMaze : to楼上，如果非２为底呢？ 12/11 16:12
: → MMaze : 另外，为什麽2^(2^N)比N!大？阶乘不是复杂度最高吗? 12/11 16:12
关於这个，阶乘的大小估计，众人来来去去用的大多是同一招：
Stirling's Formula (或称 Stirling's Approximation)
Link:
https://en.wikipedia.org/wiki/Stirling%27s_approximation
公式长这样：
√(2πN)*(N/e)^N*e^(1/(12N+1)) < N! < √(2πN)*(N/e)^N*e^(1/(12N+1))
所以大致上你可以用
N! ~ √(2πN)*(N/e)^N
满方便的
--
角卷绵芽给予炭治郎的建议
https://i.imgur.com/0mPdESk.jpg
https://i.imgur.com/Ts4dBjy.jpg
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 98.45.135.233 (美国)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1639449867.A.3C3.html
1F：推 LPH66 : 我比较喜欢两边取 log 之後记 log(N!) = O(N log N) 12/14 11:56