标准差(Standard Deviation)与四分位距(IQR)计算的大O时间复杂度是多少

你的判断基本准确，两个指标的时间复杂度可以分情况明确如下：

标准差（Standard Deviation） #

计算标准差的时间复杂度确实为 O(n)。
整个计算过程仅需对数据集做线性遍历即可完成，无需排序、分块等额外操作：

• 第一轮遍历统计所有样本值的总和，除以样本量得到均值
• 第二轮遍历计算每个样本与均值的差值平方和，再根据总体/样本标准差的公式做归一化、开方得到最终结果
  两轮遍历的总操作数和数据量n呈严格线性关系，不存在更高开销的步骤，也没有渐近意义上更优的计算方式。

四分位距（Interquartile Range, IQR） #

你提到的 O(n log n) 是工业界通用实现下的标准时间复杂度，这个结论在绝大多数实际场景下成立：

• 通用统计库的默认实现逻辑是先对全量数据集做比较排序（目前最优的比较排序算法渐近复杂度为O(n log n)），排序完成后直接按索引位置取出第25百分位数（Q1）和第75百分位数（Q3），二者做差得到IQR，取分位数的步骤仅需常数时间，整体复杂度完全由排序步骤主导。
• 补充说明：理论上存在基于快速选择（Quickselect）改进的线性时间分位数查找算法，可以将IQR计算的渐近复杂度降到O(n)，但这类算法实现复杂度高、常数项开销大，且存在最坏情况复杂度退化到O(n²)的问题，几乎不会被通用统计工具作为默认方案，因此日常讨论默认实现的复杂度时，O(n log n)的判断完全正确。

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