[考題] 99台糖/資料結構/時間複雜度

[skyw830 (.....)]

1.考試科目：資料結構

2.『出處』：99台糖資料結構第四題第二小題

3.題目內容：
有A和B二個演算法，A演算法的時間複雜度為O(nlogn)，B演算法的時間複雜度為O(n^2)，
當n為100時，B演算法所需時間為A演算法的2倍，則n為1000時，
B演算法所需時間為A演算法的幾倍?

4.想法：
  時間複雜度和所需時間成正比
  n=100時，代入O(nlogn)和O(n^2)，如何算就不是2倍
  n=1000就算不出來了，總覺的怪怪的
  不知那裡觀念不正確，煩請高手可說明一下嗎?謝謝。


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.40.82.73
推 eshinny:BIG O只是一種概念...不能代進算吧100n=1000n=O(n)吧
推 Snou:常數~   O(nlogn)真正執行時間可能是C1*nlogn + C2*n + C3
→ skyw830:知道不能代入算，所以才說和時間成正比，想不懂為何2倍?
→ eshinny:如果100你能算出兩倍，他還需要問1000嗎
→ Snou:A演算法的實際執行時間如果是25*nlogn B是n^2 n=100就是2倍啦
→ eshinny:樓上的，是50不是25
→ Snou:雖然不是重點 不過25沒錯吧 25*100*2=5000
→ eshinny:對齁，忘記兩倍。是我數學老師常請假，跟你說報歉
→ leiyan:答案是20嗎Q.Q
→ Kiotomoz:無解, 因為你不知道100/1000夠不夠大到比n0還大.
→ Kiotomoz:e.g. ta = 25nlogn + 2mole*n, tb = n^2 + 1mole*n
→ Kiotomoz:在這個情況100/1000時ta/tb就都大約2倍,直到n很大......
推 joeyeh:樓上真的知道big-O的定義嗎??
→ Kiotomoz:ITA,pp.44,"O(g(n)) = {f(n): there exist positive
→ Kiotomoz:constants c and n_0 such that <=f(n) <=cg(n) for all
→ Kiotomoz:n>=n_0}, 對耶, 我把常數放混到其他定義去了....(逃)
→ Kiotomoz:不過推論還是沒什麼問題ta/tb那樣設還是O(nlogn),O(n^2)
→ Kiotomoz:不過理由是在c,n0的類型是另一種.