这个问题并不真正取决于您运行的算法类型，它处理算法的计算复杂性，因此它更适合 StackOverflow。计算机科学的人为这些问题而活，他们非常擅长这些问题……

在任何一种情况下，算法的复杂性都使用big-O 表示法来报告。通常，如果您查看算法的维基百科描述，如果边界已知，您可以找到信息。或者，它通常由算法的作者在发布时报告。

例如，对于 SVM，复杂度界限介于和之间，其中 n 是数据点的数量，d 是特征的数量，或数据的维度。（参见Python Scikit 中的 libSVM 实现）$\mathit{O}(dn^2)$$\mathit{O}(dn^3)$

如果算法具有时间复杂度，则会发生您上面描述的场景。（算法的复杂性分别针对时间和存储进行测量）。这意味着运行时间随示例的数量而变化。$O(n)$$\textit{n}$

示例（从您的算法的输入开始）：$\textit{n}$

算法 A 时间复杂度：$O(n)$

• 旧输入大小$\textit{n}$
• 旧运行时间$\textit{t}$
• 新的输入大小，$\textit{3n}$
• 新的运行时间将是$\textit{3t}$

算法 B 时间复杂度：$O(n^2)$

• 旧输入大小$\textit{n}$
• 旧运行时间$\textit{t}$
• 新的输入大小，$\textit{3n}$
• 新的运行时间将是$\mathit{9t}$

您可以对、或应用相同的规则。使用这些规则，您可以对运行时间进行粗略（最坏情况）估计。$\mathit{O}(n^3)$$\mathit{O}(n\log(n))$$\mathit{O}(n!)$

现在，事情比这更棘手一些，因为是一个上限，但不一定是一个严格的上限（参见这个StackOverflow 线程）。这意味着会告诉你最坏情况的运行时间，这取决于你的应用程序可能对你来说毫无用处，因为它对于任何明智的计划来说都太大了，你会注意到你的平均运行时间-时间实际上要低得多。$\mathit{O}$$\mathit{O}$

在这种情况下，您可能想查看您的算法是否存在 （请参阅Bachman-Landau 表示法），这是渐近紧密的上限。对于许多算法，报告了最佳、最差和平均时间复杂度。对于许多其他人来说，我们只有一个非常宽松的上限。许多机器学习算法涉及昂贵的操作，例如矩阵求逆，或在某个点上的 SVD，这将有效地确定它们的复杂性。${\Theta}$

另一个问题是复杂性忽略了常数因素，所以复杂性实际上是只要不依赖于。但显然，在实践中，或不同。$\mathit{O}(kn)$$\mathit{O}(n)$$\mathit{k}$$\mathit{n}$$k=2$$k=1e6$

编辑 1：根据@H_R 的评论修复了运行时错误

编辑 2：在使用神经网络几年后重新阅读此回复，这似乎很有教育意义，但不幸的是，考虑到这个问题，它完全没用。

是的，我们可以量化算法的复杂性。在神经网络的情况下，它是前向和后向传递所需的操作数。然而，这个问题询问的是总训练时间，而不是如果我们增加输入，向前传球需要多长时间。

训练时间取决于充分近似输入和输出之间的关系所需的时间，即您需要进行的梯度下降迭代次数以实现足够小的损失。这完全取决于您尝试逼近的函数有多复杂，以及您拥有的样本数据有多有用和多嘈杂。

它的长短是：

一种。我不相信可以提前知道训练神经网络需要多长时间，尤其是深度神经网络（尽管我确信现有的研究正在尝试这样做）。

湾。在一些训练步骤之后，甚至不可能可靠地推断训练持续时间。

C。通常不可能使用减少的输入集来训练网络并从减少的训练时间推断到完整的数据集，因为当使用少量数据进行训练时，网络通常会表现不佳。

这就是为什么人们要么在训练神经网络时手动监督他们的训练损失（tensorflow-board），要么使用不同的启发式方法来检测损失最小化何时开始趋于平稳（早期停止）。

这取决于算法的复杂性。如果它是线性算法，即，那么它很简单：如果样本需要时间进行训练，那么样本将需要时间。如果复杂度更高，例如平方，那么您需要取时间的平方：对于两倍大小的样本，您需要四倍于 n 个样本所需的时间。所以找出你的算法的复杂性（谷歌它），在一个小样本上运行以获得估计，最后进行计算以估计你需要多少时间。除样本大小外，取决于算法，维数也可能很重要。 $O(n)$$n$$t$$2n$$2t$$O(n^2)$

除了@iliasfl 的观点之外，还有一些想法：

• 如果我认为这需要很长时间，我会进行一些测试运行，这基本上可以让我像@iliasfl 建议的那样进行检查。此外，我还查看内存，因为对于我的数据，这通常会限制我可以要求的并行化。

• 我对我的模型使用重采样验证，在此期间我通常以的数量级计算代理模型。这给我留下了一个在最外层的运行时和内存中令人尴尬的并行和线性计算。反过来说：这意味着单个模型的计算时间需要在人们可以尝试的范围内。$10^3$

• 如果我不知道计算需要多长时间（以涵盖 2 个数量级的规模），我会开始问自己是否对成功应用它的方法有足够的了解。当然也有例外，例如在我的Diplom（=硕士）论文期间，我使用的方法是固定的。

• 另一个问题是：第 2 - 8 周的计算时间对模型质量和性能评估增加了多少？
  如果我们谈论这个数量级，我真的会做一些初步计算，例如学习曲线。在开始计算之前，我还要加倍确保所有参数都是应有的。我可能会重新考虑是否不能使用更快的方法。

• （取决于您的技能、任务和您使用的算法：）如果您发现计算比您预期的要慢得多，您可能想要遵循这样的说法，即更好的算法可以将事情加速几个数量级甚至减少复杂性，而并行化只会线性帮助。有时，即使是同一算法的更好实现也可以产生一两个数量级。

• 我经常开始重采样计算，并在几次迭代后获取初步结果。这使我可以继续工作（例如设置总结结果的代码、绘制图形等），同时完善最终结果。这样一来，如果整个重新采样需要一周时间，我就不会那么困扰了。

提前调整参数

只需确保您的验证独立于参数调整即可。