线性搜索（Linear search）平均复杂度为何标注n/2而非(n+1)/2

结论先行 #

这种表述没有错误，二者是不同场景下的合理表达，你的推导也完全正确。 #

具体差异原因

• 你的精确推导适用理想前提：当明确目标元素一定存在于数组内，且出现在每个位置的概率完全相等时，平均比较次数的数学精确值就是 (n+1)/2，计算逻辑和你给出的完全一致：对长度为n的数组，总比较次数是等差数列求和1+2+...+n = n(n+1)/2，除以n种等概率情况得到精确值，这个计算没有任何问题。
• 公开资料常用n/2的核心原因有两个：
  1. 复杂度分析的常规简化逻辑：大多数时候我们讨论平均复杂度，核心关注的是增长量级而非精确常系数。(n+1)/2展开后是0.5n + 0.5，常数项0.5和常系数0.5在大O表示法中都会被省略，最终平均复杂度为O(n)。很多资料在描述比较次数的近似值时，会直接省略影响极小的+1常数项，简化写成n/2，对量级的表达没有任何偏差。
  2. 更贴近实际场景的统计结果：如果把「目标元素不存在于数组中」的情况纳入平均统计，或者假设目标元素存在/不存在的概率各占50%，最终计算得到的平均比较次数会更接近n/2，这种场景下n/2反而是更贴合实际运行情况的表述。
• 二者的使用边界：如果是做算法的数学证明、精确性能压测计数这类对精度要求高的场景，需要用精确值(n+1)/2；如果是做复杂度科普、同量级算法的横向对比，用n/2完全合理，不会产生误导。

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