algorithm - 渐近时间复杂度

Question

在阅读了很多文章或答案之后，我仍然无法解决确定函数的渐近时间复杂度的问题。该函数例如是这样的:

def function(n):
    for i in range(n):
        if i == 0:
            for j in range(n):
                for k in range(10000):
                    print("output")

n 的渐近时间复杂度是多少，n 的“输出”会被写入多少次？

谢谢。

Answer 1

理论

在此示例中，即使有 3 个嵌套循环，时间复杂度也应为 O(n)。

• i 循环运行 n 次。

• j 循环运行 n 次，但前提是 i 为 0。

• k 循环运行 10000 次，但它是一个常数因子。

为了更好地解释发生的情况，让我们区分 n_i 和 n_j，即使它们都等于 n。复杂度为:

O(1 * n_j * 10000 + n_i * 1) = O(10000 * n_j + n_i) = O(n_j + n_i) = O(n + n) = O(n)

输出应打印 10000 * n 次。

使用 %timeit 检查

如果用计数器增量替换 print 调用:

def function(n):
    count = 0
    for i in range(n):
        if i == 0:
            for j in range(n):
                for k in range(10000):
                    count += 1

您可以在 IPython 中调用 %timeit，并增加 n 的值:

%timeit function(10)
5.01 ms ± 36 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit function(100)
50.4 ms ± 334 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit function(1000)
497 ms ± 1.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit function(10000)
5.03 s ± 27.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

时间似乎与 O(n) 完美匹配!

变体

如果没有 if，复杂度将为 O(n**2):

def function(n):
    for i in range(n):
        for j in range(n):
            for k in range(10000):
                print("output")

如果k在range(n)内，复杂度将为O(n**3):

def function(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print("output")