time-complexity - 内部循环迭代依赖于外部循环迭代增加为 2 的倍数的嵌套循环的 Big-O 是什么？

嵌套循环的Big-O时间复杂度是多少，其中内部循环的迭代取决于外部循环的迭代并且外部循环的迭代以2 的倍数增加？

for (long long j = 1; j < n; j *= 2) {
    for (long long k = 0; k < j; k++) {
        // Some code
    }
}

我也需要计算。

标签： time-complexitybig-ocomplexity-theory

让， $n=2^{m}$ 。所以， $j={1,2,4,8,16,...,2^m}$ 是一个几何级数。内部循环将为j的每个值迭代次数j。

Cmplexity = 内循环总迭代次数

$=1+2+4+8+16+...+2^{m}$

$=2^{m+1}-1$

$=2\times 2^{m}-1$

$=2\times n}-1$

$=O(n)$