最近刚开始看算法方面的书。看到算法分析的时候想到一个问题：
在一个乱序的数组中检索某个 key 值的 index 的算法
暴力算法的复杂度是 n
先排序再二分检索的话复杂度是 nlogn
上面是检索一次的情况，如果检索 x 次，
暴力算法的复杂度是 xn
先排序再二分检索的时候是 nlogn+xlogn，但是其中省略哪一项我有点不太明白，
按理说大多数情况应该是 n>x，所以 nlogn>xlogn，为什么最后的复杂度把 nlogn 给省略掉，成了 xlogn
萌新求详细解释~ 先谢过~
第一部分里变量是 n。第二部分里变量是 x，nlogn 相当于常量了。也就是问题转变成了，给定一个固定大小的数组时多次查询的算法复杂度。这时候 n x 和 logn x 的数量级相同，但是 logn x 的系数更小。
对
msg7086
回复
msg7086
回复
意思就是说，因为整个程序里面排序只进行了一次，所以最后复杂度里当做一个常量忽略掉？
如果上面的理解没错的话，这样得到的复杂度是不是会出现偏差，某些情况下会把很大的常数给忽略掉？
对
baboon
回复
baboon
回复
是会出现偏差，但是大 O 主要是看增量规模而不是实际性能的，如果要计算实际系数的话，要考虑的东西会多得多，不仅仅是 n 和 x，还要考虑每一步的实际 CPU 和内存消耗，比如排序的 nlogn 的系数（数据移动和读取比较）就比查询的系数（只读取和比较）大；甚至有些排序还要新开内存区段，还要执行递归等等。
大 O(x) 的意思是对于 x 的增长，整体耗时也是线性增长。如果是 O(x^2)，则说明 x 增长时整体耗时增长是平方级的。具体系数不是大 O 要考虑的东西。