[理工] Big-O速度比较 s9e0ay917 PTT批踢踢实业坊

楼主: s9e0ay917 (Meg) 2018-04-19 19:41:48

https://i.imgur.com/kw46rez.jpg
弱弱的想请教
如图，题目感觉怪怪的
即便n小于等于100
只要n大于1，n^2必定大于n(log n)
这样program A应该恒慢于B吧？
还是要考量空间上的问题?

作者: alan23273850 2018-04-19 19:55:00

系数阿，倍率的不同

作者: wilson50101 (我觉得我还不错啊) 2018-04-19 20:10:00

我也觉得怪怪 1楼能详细一点吗？

作者: opov (信雷姆教得蕊懒叫) 2018-04-19 23:33:00

假设A是n^2好了，B是50*n*logn，在初期可能B会比较慢时间复杂度毕竟是看趋近于无限大的情况下就像在样本数少的情况下，selection sort或bubble sort可能比一些nlogn的sorting方式还来的快

作者: alan23273850 2018-04-19 23:57:00

对，如同opov大大说的，复杂度是看 n 很大的时候才叫做 "asymptotic complexity"拿 n^2 和 10*n*logn 比较，就符合题目的门槛n<=100这就是我说的系数(常数)

继续阅读