作者s9e0ay917 (Meg)
看板Grad-ProbAsk
標題[理工] Big-O速度比較
時間Thu Apr 19 19:41:48 2018
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1524138111.A.48A.html
1F：推 alan23273850: 係數阿，倍率的不同 04/19 19:55
2F：推 wilson50101: 我也覺得怪怪 1樓能詳細一點嗎？ 04/19 20:10
3F：→ opov: 假設A是n^2好了，B是50*n*logn，在初期可能B會比較慢 04/19 23:33
4F：→ opov: 時間複雜度畢竟是看趨近於無限大的情況下 04/19 23:34
5F：→ opov: 就像在樣本數少的情況下，selection sort或bubble sort可能 04/19 23:36
6F：→ opov: 比一些nlogn的sorting方式還來的快 04/19 23:36
7F：→ alan23273850: 對，如同opov大大說的，複雜度是看 n 很大的時候 04/19 23:57
8F：→ alan23273850: 才叫做 "asymptotic complexity" 04/19 23:58
9F：→ alan23273850: 拿 n^2 和 10*n*logn 比較，就符合題目的門檻n<=100 04/19 23:59
10F：→ alan23273850: 這就是我說的係數(常數) 04/20 00:00