推 teexit :感謝 04/22 01:18
※ 引述《teexit (獃獃)》之銘言：
: 在演算法中會需要計算big o
: 不過有個數值我不知道要怎麼計算他
: 2^[sqrt(2*lgn)] 想請問一下 他的big o會是甚麼呢?
: 還有需要怎麼計算他... 找不到一個可以拆解他的方式
: lg n => 以2為底的log
: 感謝
big O 給的會是上界，
所以我們可以用比較差的估計：
2 ^ (sqrt(2 * lg n)) <= 2 ^ lg n = n if n >= 4,
所以我們有 upper bound O(n)。
如果要更準確的就有點尷尬，
2 ^ (sqrt(lg n)) 是個界在 n 與 log n 之間的東西，
通常就直接這樣寫了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.15.15