1

当你有代码时：

for(int i = 0; i<N; i++)
{
   array[i] += N
}

不是每次循环迭代时都比较变量 i 和 N 吗？就此而言，不是每次循环迭代时都会向 i 添加 1 吗？

那么，这不是每次循环迭代 3 次操作吗？

为什么我们通常忽略这些操作并说这段代码是 O(n) ？这与这些操作如何使用 CPU 有关吗？

4

5 回答 5

12

Big-O 表示法不处理操作的实际成本，而是该成本如何随着问题的大小而增长。在这个程度上，O(n)并不意味着成本是n，而是成本随着问题的大小线性增长。无论 100 个元素的成本是多少，200 的成本将翻倍，1000 的成本将翻倍。同样的方式O(n^2)意味着成本呈二次方增长，因此如果问题的规模翻倍，则运算成本翻倍，如果规模增加 10 倍，成本增长百倍。

常量在这里并不重要，它们通常被排除在外。此外，在许多分析中，成本甚至不是以实际时间或内存成本表示，而是其他操作的成本。例如，无论键类型如何，std::map::find都说该函数具有。O( log N )原因完全相同：O( log N )意味着无论在包含N元素的地图中查找的成本是多少，它都会以对数方式增长。

举一个励志的例子，考虑一个相当荒谬的问题：从整本书的内容中找到一本书的作者，以及两个实现。在第一个实现中，您使用 astd::map<std::string, std::string>其中第一个std::string是书的内容，第二个是作者的姓名。第二个实现将书的内容散列成一个整数并将其存储到一个 unorderedstd::vector< std::pair<int, std::string> >中，int即散列和std::string作者姓名（假设没有散列冲突）。在地图中找到书的O( log N )作者的成本是 ，在向量中找到作者的成本是O( N )，哪个更差。但是，这些成本隐藏了比较的复杂性，在地图中比较整本书内容的成本可能是巨大的与比较哈希的成本相比，一本书的内容的单个比较可能比向量案例中所需的所有比较更昂贵。

Big-O 表示法只处理成本如何随着问题的大小而增长，并隐藏每个操作的实际成本。在分析算法的复杂性时，会忽略单个成本，但您仍应注意它们，因为 Big-O 表示法并不能说明全部情况，运行算法的实际成本将在那些恒定成本中产生你在分析中忽略了。

于 2012-06-21T22:40:38.830 回答
6

Big-O 表示法可以删除所有常数因子。调用一次迭代的比较、加法和所有其他开销c。总运行时间为cn，O(cn) = O(n)当丢弃常数因子时。

这个数学技巧用于比较将在大型数据集上工作的函数。时间复杂度为 的算法O(n^2)很可能比O(n)处理小型数据集的算法更快（如果后者的常数因子很大），但无论算法如何，小型数据集通常都能快速处理。有趣的是当数据集增长时会发生什么——搜索十亿条记录需要十秒钟还是需要几年时间？这在很大程度上受时间复杂度的影响。

于 2012-06-21T22:18:16.697 回答
6

Big-O[*] 的定义：

对于两个函数f, 和g,f(n)是O(g(n))当且仅当存在 numbersM时，c这样：

for all n > M, |f(n)| <= c * |g(n)|

（其中|x|是 的绝对值x）。

因此，从这个定义很容易看出，函数3*n是O(n)：随便取一个你喜欢的c = 3任何积极的东西。M

关于“增长率”的解释几乎是胡扯（或者实际上，它们是上述定义的动机），但它们可能有助于形成 Big-O 工作原理的直观概念。

为什么允许一个常数因子？为什么不定义那f是O(g)only if |f(x)| < |g(x)|for n > M？有几个原因 - 首先是因为“增长率”华夫饼/动机：我们真正用大 O 表示法说的是当你加倍n、三倍等时会发生什么。其次是因为“操作”的概念不是很明确。将 1 加到整数上所花费的时间与比较或跳转所用的时间不同。它甚至不一定需要相同数量的 CPU 指令。那你要测量什么？秒？CPU周期？在什么 CPU 上，以什么速度运行，以什么总线带宽？如果算法 A 在 x86 上稍微快一点怎么办？而算法 B 在 ARM 上稍微快一点？那么他们中的任何一个的时间会是Big-O（另一个的时间）吗？

对于抽象分析，我们需要比较不植根于任何特定硬件的算法的方法，Big-O 就是其中之一。

因此，算法的大 O 复杂度与每个循环执行三个恒定时间操作还是一百万次无关。他们还是贡献O(n)时间，随便挑个够大的c。

如果您log(n)按循环执行操作（循环n时间），那么您将不再是O(n)，因为对于 any c，最终log(n) > c对于足够大的n。因此不存在任何M和c满足条件。n * log n不是O(n)。

[*] 因为它适用于算法的复杂性——当接近无穷大以外的极限时也会使用 Big-O，但我们并不关心这一点。

于 2012-06-22T01:00:55.953 回答
0

我们说它与 n 成正比，因为 n 接近无穷大。因此，我不知道它们在您的处理器上花费多长时间的 n*（4 次操作）与 n 成正比。

于 2012-06-21T22:18:24.763 回答
0

常数因子等于 2 还是 2^10 并不重要。最重要的是“与不断增长的 n 相比，执行时间将如何增长”。由于代码将由编译器优化这一事实，常量因子也被删除。您不能确定优化后c仍然等于 3。

我建议您熟悉 www.coursera.orgAlgorithms: Design and Analysis, Part I在线课程。有几个（简短的）关于删除常数因子和大 O 符号的讲座。

于 2012-06-21T22:27:26.780 回答