为什么 O(2n^2) 和 O(100 n^2) 的算法复杂度与 O(n^2) 相同？

我是算法分析领域的新手。我在 Stack Overflow 问题中读到这里 ”“Big O”符号的简单英语解释是什么？ https://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o" that O(2n^2) and O(100 n^2)与O(n^2)。我不明白这一点，因为如果我们取 n = 4，则操作数将是：

• O(2 n^2)= 32 次操作
• O(100 n^2)= 1600 次操作
• O(n^2)= 16 次操作

任何人都可以解释为什么我们应该将这些不同的操作计数视为等效吗？

Why this is true can be derived directly from the formal definition https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition. More specifically, f(x) = O(g(n)) if and only if |f(x)| <= M|g(x)| for all x >= x0 for some M and x0. Here you're free to pick M as you wish, so if M = 5 for f(x) = O(n2) to be true, then you can just pick M = 5*100 for f(x) = O(100 n2) to be true.

为什么这很有用这是一个有点不同的故事。

对于常量的一些担忧很重要：

• 我们正在测量哪些操作？数组访问？算术运算？只做乘法？乘法加权的算术是加法的两倍？您可能想要使用此指标来比较算法（具有相同的 Big-O 复杂度），而事实上，即使是最有经验的计算机科学家也可能会错过操作数量上的一些细微差异。
• 假设您可以为每个操作分配合理的权重。现在必须对此达成一致，否则你会得到一些由使用不同权重的人对算法进行的几乎毫无意义的分析（除了 big-O 会给你的信息）。
• 权重可能是有时间限制的，因为操作速度会随着时间的推移而提高，并且某些操作可能会比其他操作提高得更快。
• 权重可能受环境限制，因为不同环境下的操作速度可能不同。例如，磁盘读取比内存读取慢很多。

Big-O（渐近复杂性的一部分）避免了所有这些问题。您只需检查一段需要恒定时间（即与输入大小无关）的代码被执行了多少次。例如：

c = 0
for i = 1 to n
for j = 1 to n
for k = 1 to n
  x = input[i]*input[j]
  y = input[j]*input[k]
  z = input[i]*input[k]
  c += (x-y)*z

So there are 4 multiplications, 1 subtraction and 1 addition, each executed n³ times, but here we just say that this code:

  x = input[i]*input[j]
  y = input[j]*input[k]
  z = input[i]*input[k]
  c += (x-y)*z

runs in constant time (it will always take the same amount of time, regardless of how many elements there are in the array) and will be executed O(n3) times, thus the running time is O(n3).