时间复杂度中常数项忽略规则及排序扫描算法复杂度疑问

• 关于O(N)+c中的常数项：完全可以忽略，最终复杂度仍为O(N)。大O符号描述的是输入规模N趋近于无穷大时算法的渐进增长趋势，常数项c的影响会随着N的增大被无限稀释，对整体增长趋势没有决定性作用，因此可以直接舍去。

• 关于排序加扫描的总复杂度：你拆分计算的N*log(N) + N是对的，但按照大O的规则，我们只保留增长速度最快的主导项。N*log(N)的增长速度远快于N（当N足够大时，log(N)会大于1且持续增大），低阶的N项对整体趋势的影响可以忽略，因此总复杂度简化为O(N*log(N))。你推导的N*(log(N)+1)本质和N*log(N)+N等价，但按照渐进复杂度的标准写法，我们只会保留最高阶的主导项。

核心原则总结：大O符号只关注N→∞时增长最快的项，所有低阶项、常数系数、常数项都可以被忽略——这也是为什么c*O(N)能简化为O(N)，O(N)+c能简化为O(N)，N*log(N)+N能简化为O(N*log(N))的原因。

内容的提问来源于stack exchange，提问作者Mandroid