一尘不染

Big O对运行时间的粗略估计

algorithm

如果我的程序的 时间复杂度O(n ^ 2) ,那么对于n,10 ^ 6的大值,我该如何 用秒 来表示运行时间?

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

问题不是关于时间复杂度的计算…而是关于根据时间复杂度估算运行时间


阅读 211

收藏
2020-07-28

共1个答案

一尘不染

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

Big-O告诉您方法如何根据 要执行操作进行 扩展
。不知道一个操作要花多长时间。另外,CPU在并行执行某些操作时可能会好坏,这会使其变得更加困难。 __

找出性能瓶颈的 唯一 方法是执行以下操作:

  1. 观察代码运行。需要太长时间吗?
  2. 测量代码的运行。需要太长时间吗?
  3. 缩小测量范围,直到您知道代码的哪一部分是主要瓶颈。
  4. 决定是否可以更改它,您是否会摆脱它所放入的内容?

如果您还知道该代码的Big-O等级,则可以使用它来确定如果将示例数量加倍,瓶颈是否会成倍恶化。

2020-07-28