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")