[理工] 演算法時間複雜度兩題

作者: yagerbomb (ㄅD)   2020-09-18 03:04:48
https://i.imgur.com/E3kuBpk.jpg
https://i.imgur.com/K6V4IFD.jpg
第一題想問他的邏輯是不是這樣:
因為lg*n = 1+lg*(lgn) = Theta(lg*(lgn))
所以lg*n再取log應該要絕對小於lg*(lgn) 也就是 little - oh
第二題下面 sqrt(n) 變 n/3 我知道n夠大的時候會對..但為什麼是取1/3 有特別用意嗎
作者: zuchang (chang)   2020-09-18 10:27:00
第一題little-o 那邊錯 theta定義再看一次啊 抱歉 看錯題
作者: jason35512 (jason2714)   2020-09-23 18:44:00
第一題對 第二題放大沒問題,感覺是少加n>=9的條件吧

Links booklink

Contact Us: admin [ a t ] ucptt.com