PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 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這就是我說的係數(常數)
繼續閱讀
[理工] 104交大資結
wilson50101
[理工] 離散 圖論6-2清大精選範例
st945712
[理工] DS資料結構複雜度基本問題
a0953781935
[理工] 離散 Hamiltonian cycle
WachinMs
[理工] 環狀分類判斷式打法
NTUgambler
離散 關係問題 (黃子嘉課本2-1習題)
o5739201
[理工] 離散 骰子和禁位
Heyso
離散 空集合問題
o5739201
[理工] 計組 IEEE單精度
SIGNAL2017
[理工] 控制 93清大 零點判斷
snowyfairy
Links
booklink
Contact Us: admin [ a t ] ucptt.com