for-loop - 复杂性 - bigtheta 3 循环

Question

我只是解决了一个问题，但我没有解决方案，所以请问您是否可以确认我的解决方案是否正确

int h=1; int cont = 0;

for (j = 2^N; j>1; j = j/2) {
        h = h * 2;
        for (i =1; i < j; i = i*2)
           for (k=2; k<h; k++)
               cont ++;
}

我必须在 BIGTHETA 中找到那部分代码的复杂性。

所以，我分析第三个周期就是这样长大的

k -> 线性直到 = h（h 像 2^w 一样长大） - 所以复杂度是 log n。

关于第二个，第一个周期的限制是 0，所以我认为复杂度是 log n。

关于第一个 2^N = 2^N-1 所以复杂度是 n

总复杂度为 n * log n

Answer 1

您可以使用 Sigma 表示法一步一步地正式进行（我跳过了一些步骤，但如有必要，请随时询问更多详细信息）：