1. PTT
  2. Grad-ProbAsk

[理工] 資結 時間複雜度

作者: s9e0ay917 (Meg)   2018-04-20 23:26:43
https://i.imgur.com/utEyApP.jpg
這是某OCW的資結課程
想問下圖這樣的問題會是正確的嗎？
https://i.imgur.com/Je3EHK2.jpg
講義上說是對的
但是在用定義計算之後c並非整數，f(n)=/=O(n^3)
這樣這張圖是False
請問此狀況該寫True還是False?
作者: wilson50101 (我覺得我還不錯啊)   2018-04-20 23:34:00
廣義來說是對的
作者: gary70812 (1)   2018-04-20 23:34:00
看學校，我記得交大都是要最緊的
作者: Lambo1228 (ㄩㄩ)   2018-04-21 02:36:00
是對的但是不是最小的
作者: kyuudonut (善良老百姓)   2018-04-21 11:19:00
哪有分什麼廣義、精確的.... 數學定義上就是對的。
作者: bmpss92196 (bmpss92196)   2018-04-21 11:43:00
Ture吧，取n0=1,c=10 符合定義
作者: maple205 (艾瑞克)   2018-04-21 15:36:00
kyuu他是指夠不夠tight吧，不夠tight定義對也失去意義了
作者: TWkobe (中華柯比)   2018-04-22 08:11:00
楓葉本稱不夠tight叫soft bound
作者: V1V1V1V1V1V (a shit)   2018-04-24 15:04:00
ㄜ 如果非選題就寫詳細點即可
繼續閱讀
[理工] [物理］熱力學nosy0505[理工] 線代子嘉1-74範例三EXPCDR[理工] 離散 若P則QSIGNAL2017[理工] 計概thebronjames[理工] Big-O速度比較s9e0ay917[理工] 104交大資結wilson50101[理工] 離散 圖論6-2清大精選範例st945712[理工] DS資料結構複雜度基本問題a0953781935[理工] 離散 Hamiltonian cycleWachinMs[理工] 環狀分類判斷式打法NTUgambler

Links booklink

Contact Us: admin [ a t ] ucptt.com