作者s9e0ay917 (Meg)
看板Grad-ProbAsk
标题[理工] Big-O速度比较
时间Thu Apr 19 19:41:48 2018
https://i.imgur.com/kw46rez.jpg
弱弱的想请教
如图，题目感觉怪怪的
即便n小於等於100
只要n大於1，n^2必定大於n(log n)
这样program A应该恒慢於B吧？
还是要考量空间上的问题?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.136.63.223
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1524138111.A.48A.html
1F：推 alan23273850: 系数阿，倍率的不同 04/19 19:55
2F：推 wilson50101: 我也觉得怪怪 1楼能详细一点吗？ 04/19 20:10
3F：→ opov: 假设A是n^2好了，B是50*n*logn，在初期可能B会比较慢 04/19 23:33
4F：→ opov: 时间复杂度毕竟是看趋近於无限大的情况下 04/19 23:34
5F：→ opov: 就像在样本数少的情况下，selection sort或bubble sort可能 04/19 23:36
6F：→ opov: 比一些nlogn的sorting方式还来的快 04/19 23:36
7F：→ alan23273850: 对，如同opov大大说的，复杂度是看 n 很大的时候 04/19 23:57
8F：→ alan23273850: 才叫做 "asymptotic complexity" 04/19 23:58
9F：→ alan23273850: 拿 n^2 和 10*n*logn 比较，就符合题目的门槛n<=100 04/19 23:59
10F：→ alan23273850: 这就是我说的系数(常数) 04/20 00:00