[其他] big O 大於的證明

看板Math作者 (梅姬?沒雞?傻傻分不清楚)時間3年前 (2022/09/12 05:44), 編輯推噓2(2推 0噓 2→)
留言4則, 3人參與, 3年前最新討論串1/2 (看更多)
O(N^(N/2)) < O(N!) 這個要如何證明 ? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.92.165 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1662932666.A.5CB.html
推
09/12 05:57, 3年前 , 1F
用 Stirling's Formula 去估計 N!
09/12 05:57, 1F
→
09/12 12:13, 3年前 , 2F
取log也行
09/12 12:13, 2F
推
09/12 20:19, 3年前 , 3F
兩者是一樣的意思, Stirling 的估計大致可以寫成
09/12 20:19, 3F
→
09/12 20:20, 3年前 , 4F
log(N!) = O(N log N), 用這個下去比較
09/12 20:20, 4F
‣ 更多 magic704226 的文章
文章代碼(AID): #1Z7bQwNB (Math)
‣ 更多 magic704226 的文章
文章代碼(AID): #1Z7bQwNB (Math)