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

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外循环迭代。