0

为了与每个人保持一致，这是一个家庭作业。我不希望任何人为我提供彻底的答案，这更多是为了检查我是否正确理解事物或找出我做错了什么。

我得到了一些代码片段来确定它们的 Big-Oh 是什么。每个都在处理 for 循环，但是我们得到的最后两个让我有点失望。首先：

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

我认为其中的 Big-Oh 将是 O(n^4)。#1 将运行 n 次，#2 将运行 n^2 次，#3 将运行 n 次，给我 n^4。但是，当我在 C++ 中正确编写并给出 n 值 10、100 和 1000（根据我的分配）时，n = 10 返回 7524（好，小于 10,000）n = 100 返回值 975,002,490，而上限将是 100,000,000。显然，我在对循环的分析中偏离了某个地方，但我不太确定在哪里。不确定 n = 1000 会返回什么，因为我的计算机已经运行了一段时间，而且似乎还没有准备好给我答案。

第二个片段如下：

   sum = 0;
      for (i = 0; i < n; i++) //1
         for (j = 0; j < i * i; j++) //2
            if (j % i == 0) //3
               for (k = 0; k < j; k++) //4
                  sum++;

我相信我可以放心地忽略 if 语句，因为它的运行时间是测试的运行时间加上它的内容，这意味着我会再次提出 O(n^4)。

4

1 回答 1

0

好吧，我不是 O 专家，但我知道 for 循环和一些数学，所以我会尽力帮助你。

当您考虑您的陈述“#1 将运行 n 次，#2 将运行 n^2 次，#3 将运行 n 次，给我 n^4”时，它只是部分正确.. 是的，如果这些数字几乎是正确的你分别运行循环。但是考虑 n = 4 的示例...首先#1 将运行 4 次，但是对于循环编号 #1 的每次迭代，循环编号 #2 将运行 i*i 次...所以..

首先当 i = 0 #2 将运行 0 次.. (j < 0*0) 然后当 i = 1 #2 将运行 1 次 (j < 1*1) 然后当 i = 2 #2 循环将运行 4 次(j < 2*2) 并且当 i = 3 #2 将运行 9 次 (j < 3*3)

所以总共 #2 将运行 14 次。(0 + 1 + 4 + 9 ) 和 4^4 不是 14。这也升级到 #3 循环。

正如您所说，您对直接答案不感兴趣，我希望这可以帮助您更好地理解 for 循环。

于 2013-01-29T13:51:41.497 回答