2

我是算法分析领域的新手。我在 Stack Overflow 问题“什么是“Big O”符号的简单英文解释？ ”中读到这里，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 次操作

谁能解释为什么我们应该将这些不同的操作计数视为等效？

4

3 回答 3

9

为什么这是真的可以直接从正式的定义中得出。更具体地说，f(x) = O(g(n))当且仅当|f(x)| <= M|g(x)| for all x >= x0对于某些M和x0。在这里，您可以随意选择M，因此如果M = 5为真，那么您可以选择为真。f(x) = O(n2)M = 5*100f(x) = O(100 n2)

为什么这很有用是另一回事。

有常量的一些问题很重要：

  • 我们正在测量哪些操作？数组访问？算术运算？只有乘法？乘法加权的算术是加法的两倍？您可能希望使用此指标比较算法（具有相同的 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 3次，但这里我们只说这段代码：

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

以恒定时间运行（无论数组中有多少元素，它总是花费相同的时间）并且将被执行次数，因此运行时间为.O(n3)O(n3)

于 2013-09-02T12:11:59.560 回答
3

因为O(f(n))意味着上述功能受到一些常数时间的限制f(n)。如果g以 的倍数为界100 f(n)，则也以 的倍数为界f(n)。具体来说，O(2 n^2)并不意味着它不大于 16 n = 4，而是说它不大于某些 固定的、独立于 的。nC * 2n^2Cn

于 2013-09-02T11:48:24.190 回答
1

因为它是一个分类，所以它把算法放在一些复杂的类别中。类有O(1)、O(n)、O(n log n)、O(n ^ 2)、O(n ^ 3)、O(n ^ n)等。根据定义，有两种算法在如果当 n 趋于无穷大时差异是一个常数因子，则相同的复杂度类（大哦符号用于比较较大 n 值的算法复杂度）。

于 2013-09-02T11:48:43.870 回答