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

我经历了一些实践问题，很难理解如何为下面给出的循环函数分析这些函数的运行时间。有人能帮我一步一步地完成这件事吗？
对于下面给出的每个函数，我必须给出以下每个代码片段的运行时间的增长顺序（作为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++;

最佳答案

案例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。由于外环的值小于cc>，因此总功由下式给出：

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

案例3

 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))

关于java - 分析嵌套循环运行时间？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26209842/