作者s9e0ay917 (Meg)
看板Grad-ProbAsk
標題[理工] 資結 時間複雜度
時間Fri Apr 20 23:26:43 2018
https://i.imgur.com/utEyApP.jpg
這是某OCW的資結課程
想問下圖這樣的問題會是正確的嗎？
https://i.imgur.com/Je3EHK2.jpg
講義上說是對的
但是在用定義計算之後c並非整數，f(n)=/=O(n^3)
這樣這張圖是False
請問此狀況該寫True還是False?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.67.124
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1524238005.A.582.html
※ 編輯: s9e0ay917 (223.136.67.124), 04/20/2018 23:27:00
1F：推 wilson50101: 廣義來說是對的04/20 23:34
2F：推 gary70812: 看學校，我記得交大都是要最緊的04/20 23:34
3F：→ wilson50101: 但是這樣不夠精準O(n2)才是最精確的04/20 23:34
4F：推 Lambo1228: 是對的但是不是最小的04/21 02:36
5F：推 kyuudonut: 哪有分什麼廣義、精確的.... 數學定義上就是對的。04/21 11:19
6F：推 bmpss92196: Ture吧，取n0=1,c=10 符合定義04/21 11:43
了解，這樣是我計算錯了，感謝!!
※ 編輯: s9e0ay917 (223.136.74.82), 04/21/2018 13:55:57
7F：推 maple205: kyuu他是指夠不夠tight吧，不夠tight定義對也失去意義了 04/21 15:36
8F：推 TWkobe: 楓葉本稱不夠tight叫soft bound 04/22 08:11
9F：推 V1V1V1V1V1V: ㄜ 如果非選題就寫詳細點即可 04/24 15:04