[理工] Big-O速度比較

看板Grad-ProbAsk作者 (Meg)時間7年前 (2018/04/19 19:41), 編輯推噓2(2推 0噓 8→)
留言10則, 3人參與, 7年前最新討論串1/1
https://i.imgur.com/kw46rez.jpg
弱弱的想請教 如圖，題目感覺怪怪的 即便n小於等於100 只要n大於1，n^2必定大於n(log n) 這樣program A應該恆慢於B吧？ 還是要考量空間上的問題? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.63.223 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1524138111.A.48A.html
推
04/19 19:55, 7年前 , 1F
係數阿，倍率的不同
04/19 19:55, 1F
推
04/19 20:10, 7年前 , 2F
我也覺得怪怪 1樓能詳細一點嗎？
04/19 20:10, 2F
→
04/19 23:33, 7年前 , 3F
假設A是n^2好了，B是50*n*logn，在初期可能B會比較慢
04/19 23:33, 3F
→
04/19 23:34, 7年前 , 4F
時間複雜度畢竟是看趨近於無限大的情況下
04/19 23:34, 4F
→
04/19 23:36, 7年前 , 5F
就像在樣本數少的情況下，selection sort或bubble sort可能
04/19 23:36, 5F
→
04/19 23:36, 7年前 , 6F
比一些nlogn的sorting方式還來的快
04/19 23:36, 6F
→
04/19 23:57, 7年前 , 7F
對，如同opov大大說的，複雜度是看 n 很大的時候
04/19 23:57, 7F
→
04/19 23:58, 7年前 , 8F
才叫做 "asymptotic complexity"
04/19 23:58, 8F
→
04/19 23:59, 7年前 , 9F
拿 n^2 和 10*n*logn 比較，就符合題目的門檻n<=100
04/19 23:59, 9F
→
04/20 00:00, 7年前 , 10F
這就是我說的係數(常數)
04/20 00:00, 10F
‣ 更多 s9e0ay917 的文章
文章代碼(AID): #1Qs81_IA (Grad-ProbAsk)