algorithm - 家庭作业 - 大 O 符号和计算时间

Question

假设我有一个算法，当 n = 20 时需要 0.5 毫秒，我想计算出当 n = 40 时 O(n^2) 需要多长时间。

据我了解，流程如下:

t = 0.5 * (40^2/20^2)

但这是为什么呢？我不明白这背后的机制。我知道 Big O 是一个上限，对于任何 n，它都是一些指令的输出。但是计算时间没有意义。

Answer 1

let's say I have an algorithm that takes 0.5ms for n = 20, and I want to figure out how long it takes if n = 40 for O(n^2).

不幸的是，您几乎无法推断出 n = 40 的行为。

算法是 O(n²) 的声明意味着存在一些常数 c > 0 对于足够大的n，运行时间不大于c n²。因此，您不知道 20、40 或 4,000,000 是否落入“足够大”n，即使落入，您也只能知道它在上方受某物限制。

But calculating the time isn't making sense.

不幸的是，这是一个合乎逻辑的结论。

---

编辑

感谢 Anmol Singh Jaggi 的精彩评论(非常感谢!)，这是他链接到的说明问题的图