java - 分析嵌套循环运行时间？

Question

我正在经历一些练习题并且很难理解如何分析下面给出的循环函数的运行时间。有人可以为我逐步完成整个过程吗？

对于下面给出的每个函数，我必须给出以下每个代码片段的运行时间的增长顺序(作为 N 的函数)？

int sum = 0;
for(int n = N; n>0; n/=2) 
 for(int i =0; i <n; i++)
  sum++; 

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


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

Answer 1

案例一

int sum = 0;
for(int n = N; n>0; n/=2) 
 for(int i =0; i <n; i++)
  sum++; 

当外层循环的值n固定时，内层循环所做的功为n。由于外循环取值 N, N/2, N/4, ..., N/2^⌊log(N)⌋，完成的总工作量为:

  N, N/2, N/4, ..., N / 2^⌊log(N)⌋
= N * (1 + 1/2 + 1/4 + ... 1 / 2^⌊log(N)⌋)
< 2N
= O(N)

案例2

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

当外层循环的值 i 固定时，内层循环所做的功为 i。由于外层循环采用值 1, 2, 4, ..., 2^(⌊log(N)⌋)，因此完成的总工作由下式给出:

  1, 2, 4, ..., 2^(⌊log(N)⌋)
= 2^(⌊log(N)⌋+1) - 1
= 2 * 2^⌊log(N)⌋ - 1
< 2 * 2^log(N)
= O(N)

案例三

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

无论外循环 i 取什么值，内循环所做的功都是 N。由于外循环取值 1, 2, 4, ..., 2^(⌊log(N) ⌋)，完成的总工作量由外层循环的可能值的数量乘以 N 得出，因此完成的总工作量为:

O(log(N)) * N = O(N log (N))