内循环对外循环中的每个 log(N) 进行计数时的时间复杂度

Question

考虑这个函数：

void func()
{
    int n;
    std::cin >> n;
    int var = 0;

    for (int i = n; i > 0; i--)
        for (int j = 1; j < n; j *= 2)
            for (int k = 0; k < j; k++)
                var++;
}

如果n是常数我认为时间复杂度是O(n^2 * log n) 但是当 n 是 2^m 时，我很难想象它有多复杂。

如何分析这个函数的复杂度？

Answer 1

n 不是常量，它是动态的，所以这是您分析中的变量。如果它是常量，那么无论其值如何，您的复杂度都将是 O(1)，因为在复杂度分析中所有常量都被丢弃。

同样，“n 是 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 * log(n) * (n / log(n))) => O(n^2)。

前两个循环很简单（如果第二个循环不明显，它是对数的，因为重复乘以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()

由此产生的情节是：

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

内循环对外循环中的每个 log(N) 进行计数时的时间复杂度

Time complexity when inner loop counts up for each log(N) in an outer loop

c++

time-complexity