n不是一个常数，它是动态的，所以它是分析中的变量。如果它是常数，那么不管它的值是多少，复杂度都是O（1），因为在复杂度分析中所有的常数都被丢弃了。
类似地，“n is 2^m”有点无意义，因为m在代码中不是变量，所以我不确定如何分析它。您不必引入更多变量。
让我们分解这些循环，然后将它们相乘：

for (int i = n; i > 0; i--) // O(n)
    for (int j = 1; j < n; j *= 2) // O(log(n))
        for (int k = 0; k < j; k++) // O(n / log(n))

总时间复杂度：时间复杂度为O（n）。
前两个循环是平凡的（如果第二个循环不明显，它是对数的，因为重复乘以2，序列是1, 2, 4, 8, 16...）。
第三个循环更难分析，因为它运行在j上，而不是n上。我们可以通过完全忽略最外层循环来简化问题，分析内层循环，然后将两个内层循环的复杂度乘以最外层循环的O（n）。
诀窍是查看封闭循环的形状;当j循环接近n时，k从0..n开始线性运行，k循环的基线时间为O（n）。这一时间由一个对数因子j缩放，即O（log（n））。对数因子抵消后，内部循环的时间为O（n）。
以下是一些关于内部循环复杂性的经验证据：

import math
from matplotlib import pyplot

def f(N):
    count = 0
    j = 1
    while j < N:
        j *= 2
        count += j
    return count

def linear(N):
    return N

def linearithmic(N):
    return N * math.log2(N) if N else 0

def plot_fn(fn, n_start, n_end, n_step):
    x = []
    y = []

    for N in range(n_start, n_end, n_step):
        x.append(N)
        y.append(fn(N))

    pyplot.plot(x, y, "-", label=fn.__name__)

def main():
    max_n = 10 ** 10
    step = 10 ** 5

    for fn in [f, linear, linearithmic]:
        plot_fn(fn, 0, max_n, step)

    pyplot.legend()
    pyplot.show()

if __name__ == "__main__":
    main()

由此产生的图为：

这表明，最里面的两个循环（蓝色）是线性的，而不是线性的，一旦最外面的线性循环被重新引入，就证实了整体的二次复杂性。