渐近时间复杂度

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的"output"要写多少次？

谢谢。

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

渐近时间复杂度

Asymptotic time complexity

algorithm

python-3.x

big-o

asymptotic-complexity

理论

检查 %timeit

变化