[理工] Big-O速度比較

作者: s9e0ay917 (Meg)   2018-04-19 19:41:48
https://i.imgur.com/kw46rez.jpg
弱弱的想請教
如圖,題目感覺怪怪的
即便n小於等於100
只要n大於1,n^2必定大於n(log n)
這樣program A應該恆慢於B吧?
還是要考量空間上的問題?
作者: alan23273850   2018-04-19 19:55:00
係數阿,倍率的不同
作者: wilson50101 (我覺得我還不錯啊)   2018-04-19 20:10:00
我也覺得怪怪 1樓能詳細一點嗎?
作者: opov (信雷姆教得蕊懶叫)   2018-04-19 23:33:00
假設A是n^2好了,B是50*n*logn,在初期可能B會比較慢時間複雜度畢竟是看趨近於無限大的情況下就像在樣本數少的情況下,selection sort或bubble sort可能比一些nlogn的sorting方式還來的快
作者: alan23273850   2018-04-19 23:57:00
對,如同opov大大說的,複雜度是看 n 很大的時候才叫做 "asymptotic complexity"拿 n^2 和 10*n*logn 比較,就符合題目的門檻n<=100這就是我說的係數(常數)

Links booklink

Contact Us: admin [ a t ] ucptt.com