java - 如何确定嵌套循环中的语句执行的频率？

Question

我正在阅读一段关于使用递归关系确定嵌套循环复杂性的文本。在这个特定示例中，我试图确定计数变量将作为 n 的函数递增多少次。

这是我正在分析的循环：

for (int i = 1; i <= n; i++) {
     int j = n;
     while (j > 0) {
           count++;
           j = j / 2;
     }
}

我想我明白第一行将简单地等同于 n 因为它只针对 n 的每个值执行，但其余的部分我遇到了麻烦。我认为答案类似于 n(n/2) ，只是这个例子使用的是整数除法，所以我不确定如何用数学表示。

我已经在纸上手动运行了几次循环，所以我知道对于 1-6 的 n 值，计数变量应该等于 1、4、6、12、15 和 18。我似乎无法想出公式......任何帮助将不胜感激！

score 2 · Accepted Answer

循环n在范围内执行[1, n]。对于设置为 n的变量，它每次除以 2 j，因此内部循环执行的次数是floor(l2(n)) + 1,其中 l2 是二进制 log 函数。将所有这些值从 1 加到 n（乘以n）。

score 0 · Accepted Answer

内部j循环将第一个设置位的位置添加到计数中。

每次除以 2 与右移相同，直到所有位都为零。

因此，2 在二进制中是 10，内部循环的值为 2。4 在二进制中是 100，内部循环的值为 3。

外部循环似乎只是将第一个设置位的位置乘以数字本身。

这是一个 n = 13 的示例。

二进制中的 13 是 1101，所以第一个设置位在位置 4。

4 * 13 = 52。52 是最终答案。

score 0 · Accepted Answer

for (int i = 1; i <= n; i++) {

顶部的这个循环经过n 次循环。

 int j = n;
 while (j > 0) {
       count++;
       j = j / 2;
 }

这里的这个循环通过循环 log(n) 次，注意它是一个以 2 为底的日志，因为你每次都除以 2。

因此，计数总数为n * ceiling(log(n))

3 回答 3