增长的顺序复杂的循环 [英] Order Of Growth complicated for loops

问题描述

对于下面的代码片段，以N为单位的增长顺序是多少？

  int sum = 0; （int j = 1;j≤N; j = j * 2）
为（int i = 1;i≤N; i = i * 2）
的
 for（int k = 1; k <= i; k ++）
 sum ++; 
  

我猜想有lgN这个词， + 4 + 8 + 16 + ....）。序列的最后一项是什么？我需要最后一个期限来计算总和。

解决方案

在外部循环中有一个几何级数，所以有一个闭合

  1 + 2 + 4 + ... + 2 ^ N = 2 ^（N + 1） -  1 
  

准确地说，你的总和是

  1 + ... + 2 ^（floor（ld（N））
   
 
用 ld 表示以2为底的对数。
 
 
外部的两个循环是相互独立的，而最内部的循环只依赖于 i 。最内部循环中有一个单独的操作（增量），这意味着
 
 
  \sum_i = 1 ..（floor（ld（N ））{
 \sum_j = 1 ..（floor（ld（N）））{
 \sum_k = 1..2 ^ i {1} 
} 
} 
 
 //调整最里面的求和边界
 = （floor（ld（N）））{
 -1 + \ sum_k = 0（floor（ld（N）））{
 \ sum_j = 1 .. 
 
 
 
 //换算外部和求解最内部求和
 = \sum_j = 1 ..（floor（ ld（N）））{
 \sum_i = 1 ..（floor（ld（N）））{
 2 ^ i 
} 
} 
 
 //解析内部求和
 = \ sum_j = 1 ..（floor（ld（N）））{
 2 ^（floor（ld（N））+ 1） -  2 
 
 
 //解析外部求和
 = ld（N）* N  -  2 * floor（ld（N））
  / pre> 
 
 
这相当于 O（N log N）（表达式中的第二项渐近消失第一个）用Big-Oh表示。
 
For the following code fragment, what is the order of growth in terms of N?
int sum = 0;
for (int i = 1; i <= N; i = i*2)
  for (int j = 1; j <= N; j = j*2)
    for (int k = 1; k <= i; k++)
        sum++;
I have figured that there is lgN term, but I am stuck on evaluating this part : lgN(1 + 4 + 8 + 16 + ....). What will the last term of the sequence be? I need the last term to calculate the sum.
解决方案
You have a geometric progression in your outer loops, so there is a closed form for the sum of which you want to take the log:
1 + 2 + 4 + ... + 2^N = 2^(N+1) - 1
To be precise, your sum is
1 + ... + 2^(floor(ld(N))
with ld denoting the logarithm to base 2.

The outer two loops are independent from each other, while the innermost loop only depends on i. There is a single operation (increment) in the innermost loop, which means that the number of visits to the innermost loop equals the summation result.
  \sum_i=1..( floor(ld(N)) ) {
      \sum_j=1..( floor(ld(N)) ) {
          \sum_k=1..2^i { 1 }
      }
  }

    // adjust innermost summation bounds   
= \sum_i=1..( floor(ld(N)) ) {
      \sum_j=1..( floor(ld(N)) ) {
          -1 + \sum_k=0..2^i { 1 }
      }
  }

    // swap outer summations and resolve innermost summation
= \sum_j=1..( floor(ld(N)) ) {
      \sum_i=1..( floor(ld(N)) ) {
          2^i
      }
  }

   // resolve inner summation
= \sum_j=1..( floor(ld(N)) ) {
      2^(floor(ld(N)) + 1) - 2
  }

   // resolve outer summation
= ld(N) * N - 2 * floor(ld(N))
This amounts to O(N log N) ( the second term in the expression vanishes asymptotically wrt to the first ) in  Big-Oh notation.

                        
这篇关于增长的顺序复杂的循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！