内部循环不断增长的嵌套循环的复杂性

Question

我对这段代码的时间复杂性和用于查找它的逻辑感到困惑.

void doit(int N) {
    for (int k = 1; k < N; k *= 2) { <----I am guessing this runs O(logN)
           for (int j = 1; j < k; j += 1) { <------I am not sure how this one works.
       }
    }
}

我已经尝试用手写出来解决它了.但是,我仍然不明白.

感谢您的时间.

编辑:

添加另一个问题.相同的概念,不同的格式.

void doit(int N) {
    int j, k; //I ended up getting this answer to be O(n^(n/2)) But then I was stuck after that...is that even the right answer?
    for (k = 1; k < N / 2; k += 1) {
       for (j = k; j < 2 * k; j += 1) [
             x[j] = x[j-k] + x[j];//This doesn't really matter
        }
    }
}

Answer 1

总的复杂性实际上是 O(N)

声明:对于每个k你有k内循环迭代.(说服自己为什么这是正确的)

表示内循环迭代次数T(N),并将外循环数设为h.
这意味着我们有:

T(N) = 1 + 2 + 4 + ... + 2^h 
     < 2 * 2^h               (1)
     = 2^(h+1)     
     = 2^(logN + 1)          (2)
     = 2^(log(2N))   
     = 2N

(1)从和或几何系列
(2)注意,相等2^(h+1) = 2^(logN + 1)是因为h = logN,我们(如你所说)logN外循环迭代.