Re: [其他] 關於時間複雜度（big O）的排序

看板Math作者arrenwu (不是綿芽的錯)時間4年前 (2021/12/14 10:44)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《MMaze (Maze)》之銘言： : ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 103.232.136.184 (臺灣) : ※ 文章網址: https://www.ptt.cc/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