是否有一个已知的统计技术通用表来解释它们如何随样本大小和维度缩放？例如，前几天我的一个朋友告诉我，简单快速排序大小为 n 的一维数据的计算时间为 n*log(n)。
因此，例如，如果我们将 y 与 X 进行回归，其中 X 是一个 d 维变量，它会变成 O(n^2*d) 吗？如果我想通过精确的高斯马尔可夫解决方案与牛顿法的数值最小二乘法找到解决方案，它如何扩展？或者只是获得解决方案与使用显着性测试？
我想我更想要一个好的答案来源（比如一篇总结各种统计技术规模的论文），而不是一个好的答案。比如说，一个包含多元回归、逻辑回归、PCA、cox 比例风险回归、K-means 聚类等缩放的列表。
大多数有效（且非平凡）的统计算法本质上都是迭代的，因此最坏情况分析O()是无关紧要的，因为最坏情况是“它无法收敛”。
然而，当您有大量数据时，即使是线性算法 ( O(n)) 也会很慢，然后您需要关注符号背后的常量“隐藏”。例如，计算单个变量的方差是简单地扫描数据两次（一次用于计算均值的估计，然后一次用于估计方差）。但它也可以一次性完成。
对于迭代算法，更重要的是收敛速度和参数数量作为数据维数的函数，这是一个对收敛有很大影响的因素。许多模型/算法会增长许多参数，这些参数与变量（例如样条）的数量成指数，而其他一些则线性增长（例如支持向量机、随机森林……）
你在标题中提到了回归和 PCA，每一个都有一个明确的答案。
如果 N > P，线性回归的渐近复杂度降低到 O(P^2 * N)，其中 P 是特征数，N 是观察数。最小二乘回归运算的计算复杂性中的更多详细信息。
Vanilla PCA 是 O(P^2 * N + P ^ 3)，如Fastest PCA algorithm for high-dimensional data。然而，对于非常大的矩阵存在快速算法，在那个答案和Best PCA Algorithm For Huge Number of Features 中进行了解释？.
但是，我认为没有人编写过有关该主题的单一点燃评论或参考书或书籍。对于我的空闲时间来说，这可能不是一个糟糕的项目......
我在这篇Stata Journal 文章中根据实际模拟的时间为 Stata 开发的验证性因子分析包给出了非常有限的部分答案。验证性因子分析是作为最大似然估计技术实施的，我可以很容易地看到计算时间如何随着每个维度（样本量n、变量p数、因子数k）增长。由于它在很大程度上取决于 Stata 对数据的看法（优化为跨列/观察而不是跨行计算），我发现性能是O(n^{0.68} (k+p)^{2.4})其中 2.4 是最快的矩阵求逆渐近线（在验证性因子分析迭代最大化中有很多这样的东西）。我没有为后者提供参考，但我想我是从Wikipedia获得的。
请注意，OLS 中还有一个矩阵求逆步骤。然而，出于数值准确性的原因，没有人会真正对X'X矩阵进行暴力逆运算，而宁愿使用扫描算子并识别危险的共线变量来处理精度问题。如果你加起来最初是双精度的数字，您最终可能会得到一个只有单精度的数字。当您开始优化速度时，数值计算问题可能会成为大数据计算的一个被遗忘的角落。