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

Question

我是算法分析领域的新手。我在这里阅读 Stack Overflow 问题“What is a plain English explanation of "Big O" notation? ” O(2n^2) 和 O(100 n^2) 与 O(n^2) 相同>。我不明白这一点，因为如果我们取 n = 4，操作次数将是:

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

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

Answer 1

为什么这是真的 可以直接从 the formal definition 推导出来.更具体地说，f(x) = O(g(n))当且仅当 |f(x)| <= M|g(x)| for all x >= x0对于一些 M和 x0 .在这里你可以自由选择M如你所愿，如果M = 5对于 f(x) = O(n<sup>2</sup>)是真的，那么你可以选择M = 5*100对于 f(x) = O(100 n<sup>2</sup>)是真的。

为什么这有用有点不同。

关于常量问题的一些担忧:

• 我们要衡量哪些操作？数组访问？算术运算？只有乘法吗？乘法加权的算术是加法的两倍？您可能想使用此指标比较算法(具有相同的 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

所以有4次乘法，1次减法和1次加法，每次执行n³次，不过这里我们只说这段代码:

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

以恒定时间运行(无论数组中有多少元素，它总是花费相同的时间)并将执行 O(n<sup>3</sup>)次，因此运行时间为 O(n<sup>3</sup>) .