10 种 ML 算法的训练与推理时间复杂度

Training and Inference Time Complexity of 10 ML Algorithms

下面是 10 种最常用 ML 算法的运行时间复杂度。

但为什么要关注运行时间呢？我一直关注运行时间的原因有很多，你也应该关注它。

首先，大家都知道我们都很喜欢 sklearn 的实现。用 sklearn 跑任何一个 ML 算法，真的只需要两行（最多三行）代码。然而根据我的经验，正是因为这种简单，大多数用户往往会忽略以下两点：

• 对算法核心原理的理解。
• 允许我们使用某种算法的数据层面的前提条件。

举例来说，如果你在一个样本量很大的数据集上用 SVM 或 t-SNE，你会大吃一惊。

• SVM 的运行时间随样本总数呈立方级增长。
• t-SNE 的运行时间随样本总数呈平方级增长。

搞清楚运行时间的另一个好处是，它能帮助我们端到端地理解一个算法是怎么工作的。当然，在上面的表格里我这里那里做了一些假设。例如：

• 在随机森林（random forest）中，所有决策树（decision tree）可能有不同的深度。但这里我假设它们深度相等。
• 在 kNN（k 近邻）的推理（inference）阶段，我们首先要计算到所有数据点的距离，从而得到一个大小为 N（总样本数）的距离列表。
  • 然后，我们从这个列表中找出 k 个最小的距离。
  • 确定 k 个最小值的运行时间取决于具体实现：■ 先排序再选出 k 个最小值，复杂度为 O(N log N)。■ 但如果使用优先队列，则只需 O(N log N k)。
• 在 t-SNE 中还有一个学习步骤。由于主要运行时间来自计算高维空间中的两两相似度，所以我们忽略了那一步。尽管如此，这张表仍然准确地反映了这些算法总体上的运行时间。作为练习，我鼓励你自己推导一下这些时间复杂度。这一练习会给你在算法理解上带来极大的信心。118