java - 计算循环运行的次数

Question

如果我们有这样的循环

for(int i=0; i<n; i+=2) 
{
    total+=1;
}

我假设 header 中有一条指令，并且它执行主体中的一条指令，因此指令总数为(n-0)/2*1+1(最后一个条件)。这是正确的做法吗？你会怎么算呢？

还有，这个怎么样？

for(int i=1; i<n; i*=2)
{
    total+=1;
}

如果n = 20，i就像1,2,4,8,16，但我不知道如何计算

Answer 1

只需将它们写在纸上并寻找模式即可。对于您的第一个示例:

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

n  i's      total
0  []       0
1  [0]      1 
2  [0]      1
3  [0,2]    2
4  [0,2]    2
5  [0,2,4]  3
6  [0,2,4]  3
   and so on..

即floor((n+1)/2)(或整数除法)。

第二个；通过检查我们可以看到它与 log2 相关，因此让我们将计数与 log2(n) 进行比较，看看是否可以找到模式:

for(int i=1; i<n; i*=2)

n   i's        total   log2(n)
1   []            0     ---
2   [1]           1     1
3   [1,2]         2     1.58
4   [1,2]         2     2
5   [1,2,4]       3     2.32
6   [1,2,4]       3     2.58
7   [1,2,4]       3     2.81
8   [1,2,4]       3     3
9   [1,2,4,8]     4     3.17
10  [1,2,4,8]     4     3.32
11  [1,2,4,8]     4     3.46
12  [1,2,4,8]     4     3.58
13  [1,2,4,8]     4     3.70
14  [1,2,4,8]     4     3.81
15  [1,2,4,8]     4     3.91
16  [1,2,4,8]     4     4
17  [1,2,4,8,16]  5     4.09

看看这个并思考一下，我们可以看到它是 floor(1+log2(n-1))，特殊情况为 n=0 (total=0) 和n=1(总计=0)。

最后一个的思考过程是:我们必须将 log2 列向下“移动”一位，使其与 total 列对齐(因此 >log2(n-1))，我们必须给它加 1 以使值匹配。