4

我似乎理解了更简单循环的基本概念......第一个循环在 O(n) 中运行，内部循环也是如此。因为它们都是嵌套的，所以乘以得到 O(n^2) 的总运行时间。

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

虽然当事情开始发生转变时，我完全不知道如何解决这个问题。有人可以向我解释如何计算以下两项的运行时间吗？此外，任何可以进一步帮助我改进的易于理解的参考资料的链接也值得赞赏。谢谢！

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

我可以从中收集到的唯一信息是内部循环在 O(n) 中运行。i+=2 真的让我陷入了外循环。

sum = 0; 
for( i = 1; i < n; i *= 2 ) 
  for( j = 0; j < n; j++ ) 
    ++sum;

根据我的尝试...外循环是 O(log(n))，内循环是 O(n)，所以总是 O(n log(n))？

4

1 回答 1

2

考虑 Big-O 性能的一个好方法是假设代码的每个元素都是一个数学函数，它接受n项目并返回对这些项目执行的计算次数。

例如，一个for类似的循环for ( i = 0; i < n; i++ )相当于一个函数i()，其中i(n) = n表示对每个输入执行一次计算n。

如果您有两个嵌套循环，则功能等价于

for ( i = 0; i < n; i++ ) 
   for j = 0; j < n; j++ )

看起来像这两个函数：

i(n) = n * j(n)
j(n) = n

处理这两个函数会产生最终结果n*n = n^2，因为j(n)可以替换为n。

这意味着只要您可以解决任何单个循环的 Big-O，您就可以将这些解决方案应用于一组嵌套循环。

例如，让我们看看您的第二个问题：

for( i = 0; i < n; i += 2 ) 
  for( j = 0; j < n; j++ )

i+=2意味着对于输入的一组n项目(n0, n1, n2, n3, n4)，您只接触该组的所有其他元素。假设您初始化了i=0，这意味着您只接触了 的集合(n0,n2,n4)。这意味着您将用于处理的数据集的大小减半，并且意味着功能等价物的结果如下：

i(n) = (n/2) * j(n)
j(n) = n

解决这些让你(n/2) * n = (n^2)*(1/2)。由于这是 Big-O 工作，我们删除常量以产生 的 Big-O 值(n^2)。

这里要记住的两个关键点：

  1. Big-O 数学从一组n数据元素开始。如果您尝试确定for循环遍历该组n元素的 Big-O，则第一步是查看增量器如何更改for例程实际接触的数据元素的数量。

  2. Big-O 数学就是数学。如果您可以单独解决每个for表达式，您可以使用这些解决方案来构建您的最终答案，就像您可以解决一组具有共同定义的方程一样。

于 2012-09-12T23:52:00.417 回答