作者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/cn.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