从 Big O 粗略估计运行时间

Question

如果我的程序的时间复杂度是O(n^2)，对于 n,10^6 的大值，我如何以秒为单位表示运行时间？

我需要对此进行粗略估计以了解是否需要优化或者我可以继续我的代码....时间限制为 0.6 秒

问题不是关于时间复杂度的计算......而是关于从时间复杂度估计运行时间

Answer 1

无法根据某段代码的 Big-O 评级来计算或估计其运行时间。

Big-O 告诉您方法如何根据要执行的操作进行扩展。它不知道执行一项操作需要多长时间。此外，CPU 在并行执行某些操作方面可能是好是坏，这使得它变得更加困难。

确定是否存在性能瓶颈的唯一方法是执行以下操作：

1. 观察代码运行。是否需要太长时间？
2. 测量运行的代码。是否需要太长时间？
3. 缩小测量范围，直到您知道代码的哪一部分是主要瓶颈。
4. 决定它是否可以改变，你会从中得到你投入的东西吗？

如果您还知道该代码的 Big-O 等级，您可以使用它来确定如果您将要处理的项目数量加倍，瓶颈是否会呈指数级恶化。