complexity-theory - 大哦符号混乱

Question

我不确定这是否是我理解的问题，但 Big Oh 符号的这一方面对我来说似乎很奇怪。假设您有两种算法 - 第一种执行 n^2 操作，第二个执行 n^2-n 操作。由于二次项的优势，两种算法的复杂度都为 O(n^2)，但第二种算法总是比第一种算法好。这对我来说似乎很奇怪，Big Oh 符号使它们看起来是一样的。我不知道...

Answer 1

大 O 不是关于执行算法所需的时间，而是关于在呈现大数据集（n 的大值）时它的可扩展性。

当呈现大型数据集时，n^2 项将迅速盖过任何线性项。所以线性项变得微不足道。

Answer 2

当 n 向无穷大增长时，n^2 将比 n 大得多，因此 -n 对结果不会有任何显着差异。