算法时间复杂度的最高次幂项的系数很大怎么办假设时间复杂度多项式为a*n^3+b*n^2+c*n+d,那么其时间复杂度为O(n^3),但如果最高次项前的系数a很大,等于100,1000,10000的时候,还能把这个系数忽略吗?

Question

算法时间复杂度的最高次幂项的系数很大怎么办
假设时间复杂度多项式为a*n^3+b*n^2+c*n+d,那么其时间复杂度为O(n^3),但如果最高次项前的系数a很大,等于100,1000,10000的时候,还能把这个系数忽略吗?

Answer 1

能不能忽略取决于你想干什么
当你把a*n^3+b*n^2+c*n+d写成O(n^3)的时候说明你只关心复杂度的阶数的上界,这个时候不论a多大都能忽略
但是如果你想考察一个算法实现出来之后的具体速度,或者对两个给定的算法进行比较的时候,这些系数还是有用的,不能扔掉不管