1

我读到了 Big-O 表示法。我理解了一些想法，但是当比较两种算法时，我不明白他说现有的两种算法之后的一些事情。

 First f2(n) = 2n + 20 steps. 
second f3(n) = n + 1 steps.
he write f2 = O(f3):

    f2(n)/f3(n)
    =((2n + 20)/(n + 1))<= 20;
   he say Certainly f3 is better than f2?, of course f3 = O(f2), this time with c = 1.

我认为 f3 比 f2 更好，因为因素较少。我的问题

1）为什么常数c = 1他怎么选的？2) 为什么 f3 = O(f2) 以及为什么 f2 = O(f3) ？

4

2 回答 2

1

它们都是线性函数，所以两者都是O(n)，并且两者O都是彼此的。f3渐近地比 快 20 倍f2。所有这些事情同时是真实的。

于 2013-02-13T22:34:06.223 回答
0

Patrick87 的回答更多地解释了 Big-O 表示法的渐近性质。我将向您展示对此的更多分析。让我们更仔细地检查f2一下f3：

首先，f2(n)我们知道f2(n) = O(2n + 20)。20 是一个常数，所以我们可以忽略它。所以，f2(n) = O(2n + 20) = O(2n)。同样，2 是一个常数，所以我们也可以忽略它，所以：f2(n) = O(2n + 20) = O(2n) = O(n)。

这个分析的意思是，随着n增加，函数的增长速度与函数的2n + 20增长速度一样快，函​​数的增长速度与函数2n的增长速度一样快n。如果您考虑一下，这是有道理的：所有这些功能都是平行线。它们的增长速度是相同的。

现在f3(n)：我们知道f3(n) = O(n + 1)。1 是一个常数，所以我们可以忽略它。所以，f3(n) = O(n)。

这就是为什么f3和f2都是O(n)。这并不意味着对于给定的 值，这些函数所用的时间完全相同n，或者与时钟时间f2一样快f3。这只是意味着这两个功能的复杂性（即他们完成工作所花费的时间）以与增加相同的速度增加n。

于 2013-02-13T22:45:09.847 回答