Re: [理工] [DS]97交大

[s63056305 (NeetFish)]

※ 引述《mqazz1 (無法顯示)》之銘言：
: 標題: Re: [理工] [DS]97交大
: 時間: Mon Feb 14 17:06:53 2011
:
: ※ 引述《xygod (XY)》之銘言：
: : 我想問第四題的第2小題
: : 題目:http://www2.lib.nctu.edu.tw/n_exam/exam97/cslz/cslz1001.pdf
: : 剛剛爬文看到這題是F，原因是建heap只要O(n)
: : 可是建heap的時候不是把input 放到 array後，
: : 在跑n/2次的adjust，得到一個max(or min)heap
: : 這樣子建heap不是應該O(nlgn)嗎??
: : 不知道我觀念哪裡錯，麻煩各位救救我~~~
:

我想請問一下同一題
我這題寫True
我寫的時候也知道做一個Heap出來明明只需要O(n)

可是我看到他是用Big O 寫 O(nlgn)

既然是Big O
nlgn 比 n 大照理說也要算對才是？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 1.169.168.33
推 whenisawu:用tight去看吧@@"  這種題目寫O(nlgn)通常都是要騙你
→ whenisawu:因為可以最佳可以O(n)
→ s63056305:如果在考試的時候有寫說我知道只要用O(n)不知道會不會對
→ s63056305:可是用BigO明明是對的 這樣要我寫False實在是..
→ s63056305:而且我也怕教授就是想抓有沒有人不懂BigO
→ whenisawu:其實要看情況耶 如果是一般問你一個式子的BigO 那就要
→ whenisawu:照你平常BigO的定義去看 但是如果像這題要看複雜度
→ whenisawu:就不會這麼無聊去考你BigO的定義 而是去問你對資料結構
→ whenisawu:了解 另外這邊用BigO其實是因為複雜度如果Best
→ whenisawu:的話最upper bound 其實還是O(n)    如果O(nlgn)的
→ whenisawu:upper bound就不叫best algo.
→ s63056305:好 我了解了 XD
→ sneak: 可是用BigO明明是對 https://daxiv.com