1

我对*2第二个循环中会发生什么感到困惑。我知道第一个循环使n迭代第二个循环增加，*2所以我不确定如何确定会有多少次迭代。就像它一样+2，我相信我们会n/2为第二个循环进行迭代。

for (int count = 0; count < n; count ++)
{
    for (int count2 = 1; count2 < n; count2 = count2 * 2)
    {
        System.out.println(count, count2);
    }
}
4

1 回答 1

3

所以你得到更简单的情况：

for (int count = 0; count < n; count ++)
{
    for (int count2 = 1; count2 < n; count2 ++)
//                                   ^^^^^^^^^
    {
        System.out.println(count, count2);
    }
}

这里外循环运行n时间，内循环运行n时间，所以我们只需乘以n得到nO(n 2 )。（此代码片段中的内部循环仅运行n-1时间这一事实对顺序没有任何影响。）

所以问题是，在你的例子中，我们count2每次加倍，内循环的功能是什么？让我们调用内部循环运行时间的函数f(n)。所以我们的大 O 将是 O(nf(n))。

让我们看一下内部循环。它运行1time if n=1..2, 2times if n=3..4, 3times if nis upto 8, 4times if nis upto 16, 5times if nis upto 32. 2=>1映射,4=>2等的函数是什么8=>3？

您应该注意的是 , 2 = 2^1, 4 = 2^2,8 = 2^3等等16 = 2^4。您想要的是与 2 的幂相反，这是以 2 为底的对数（但对于大 O，对数无关紧要）。

所以f(n) = log(n)，我们有O(n log(n))。

编辑：了解正在发生的事情的最简单方法是简单地运行具有不同值的程序n。例如，n=8你得到输出：

(0,1), (0,2), (0,4)
(1,1), (1,2), (1,4)
(2,1), (2,2), (2,4)
(3,1), (3,2), (3,4)
(4,1), (4,2), (4,4)
(5,1), (5,2), (5,4)
(6,1), (6,2), (6,4)
(7,1), (7,2), (7,4)

迭代次数 = n log2(n) = 8 * 3 = 24. n这是的幂的精确关系2。在其他情况下，这种关系并不准确。例如，n=7你得到相同的输出（最后一行除外），但代码仍然是 O(n log(n))，因为你可以选择一个常数k=2，比如，使得内部循环的迭代次数为<= k n log(n)。

于 2013-09-18T22:51:23.563 回答