big-o - 计算上限和下限的见证

Question

我正在研究程序的运行时间并且遇到了大 O 符号。有人被要求通过证明存在整数和常数来证明这T(n)一点，使得对于所有整数，。O(f(n))xc > 0n >= xT(n) <= cf(n)

我看到的例子通过“挑选”x和的值来证明这一点c。我知道您可以将值插入方程式并查看它们是否正确，但是有没有办法实际计算xor c？或者，至少，一些关于如何选择它们的经验法则，这样就不会无休止地插入值？

Answer 1

这些值来自算法的检查T。例如，当您有一个简单的循环时：

for (i=0; i < n; ++i) {
  sum += i;
}

然后你执行操作i<n,++i和sum+=in 次, 和i=0一次。所以f(n)==n，c==4（对于这四个操作，为了值的正确性，将“一次”提升到“n 次”），x==1（对于n==0，您仍然执行i=0and i<n，因此该公式将不起作用）。这为您提供了 O(n) 性能（与输入数量成线性关系）。

对于嵌套循环：

for (i=0; i < n; ++i) {
  for (j=0; j<n; ++j) {
    sum += j;
  }
}

计算是相似的，用f(n)==n^2，给你 O(n^2)。

因此，没有直接的方法来告诉 和 的确切值c，x但大多数时候最难的部分是提出来的f——而且“最小的”也是（一个 O(n^2) 算法是根据您提供的定义，还有一个 O(n^3) 算法，但您想用 O(n^2) 而不是 O(n^3)) 来表征该算法。s的排序f基于它们在n接近无穷大时的增长：f(n)=n^3增长比 慢f(n)=2^n，即使对于小n的 s 前者大于后者。

请注意，理论上 和 的实际值随着接近无穷大x而c变得无关紧要n，这就是为什么它们不会出现在O(n)符号本身中的原因。但是，这并不意味着对于（相对）较小的值 if n，指令的数量不会比f(n)（例如，for 循环中有 1000 条指令）大很多。

此外，O(n) 表示法会给您带来最差的性能，例如，这可能比您在现实生活中观察到的（平均案例成本）或数据结构的整体使用（摊销成本）要高得多。