第1组：
第 1 组的复杂性/速度似乎不太难弄清楚是否使用了蛮力算法（尽管可能有更有效的替代方案，例如“跳跃式”算法）。例如，个候选特征回归来拟合。一个线性回归的 OLS 拟合具有的复杂性（根据这篇文章），其中是样本大小。因此，蛮力全子集选择的总复杂度应该是。$2^K$$K$$\mathcal{O}(K^2 n)$$n$$\mathcal{O}(2^K K^2 n)$

第2组：
第 2 组的复杂性/速度在本书的第 3.8 节和第 3.9 节中进行了讨论。例如，具有给定惩罚的岭回归具有与常规回归相同的计算复杂度。由于，因此计算负载会随着交叉验证中使用的数据拆分数量（例如）线性增加。如果网格有个点，则调整参数的岭回归的总复杂度将是。 有相当多的讨论$\lambda$$\lambda$$S$$\lambda$$L$$\lambda$$\mathcal{O}(LSK^2 n)$
LASSO在书中，但我找不到我需要的东西。但是，我在 p 上找到了。Efron 等人的 443。“最小角回归”（2004），如果使用 LARS 方法，给定的 LASSO 复杂度与线性回归的 OLS 拟合的复杂度相同。参数的 LASSO 的总复杂度将是。（我没有仔细阅读那篇论文，所以如果我错了，请纠正我。）弹性网结合了山脊和LASSO；两者具有相同的计算复杂度；因此，弹性网络的复杂度应该是其中是调整参数的网格大小$\lambda$$\lambda$$\mathcal{O}(LSK^2 n)$
$\mathcal{O}(ALSK^2 n)$$A$$\alpha$平衡 ridge 与 LASSO 的权重。

第3组：
我仍然错过关于第 3 组复杂性/速度的任何说明。它由主成分回归 (PCR) 和偏最小二乘法 (PLS) 组成。

它仅适用于上述第 3 组（即 PLS）的问题 2 的一部分，但仍然可能提供信息：Srinivasan 等人（2010 年，技术报告；参见https://www.umiacs.umd.edu/~balajiv/Papers/ UMD_CS_TR_Pls_Gpu.pdf）使用 NIPALS 算法对 PLS 进行了一些测量 - 说明该算法的时间（和空间）复杂度为 O(dN) - 用于提取并将这些包含在不同的模型中，用于 a）在图像中检测人类，以及 b ） 人脸识别。测量是使用他们自己的基于 GPU 的实现来完成的。