complexity-theory - 为什么 O(n) 等于 O(2n)

Question

我知道 O(N) 基本上等于 O(cN)，其中 c='某个常数'。但如果 N = c。那不是O（N）^ 2。这是否随着 c 的增加而成立，或者是否有一些正式的限制。

Answer 1

如果N = cthenc不是恒定的。因此，从来都不是这样。

Answer 2

O(n) 意味着算法的运行时间随着输入的大小线性增加。如果将输入的大小加倍，则运行时间也会加倍。如果将输入的大小增加三倍，则运行时间将增加三倍。等等。所以图形是一条直线。

O(n^2) 意味着算法的运行时间随着输入的大小呈二次方增加。如果将输入的大小增加一倍，则运行时间会增加四倍。这是不好的。图表类型循环起来并很快变得非常高。

使用 O(2n)，您增加了线的斜率，但它仍然是一条线。由于它是线性的，因此它“减少”到 O(n)。

希望有帮助。