python - 以下 Python 函数示例的大 O

Question

以下函数的 Big-O 是什么？

for a in range(n):
        for b in range(n - a):
            for c in range(n - b):
                if a + b + c == 0:
                    break
            if a + b == 0:
                break
        if a == 0:
            break
    return n + 1

我在想它会是 O(N^3)，因为有一个三重嵌套的 for 循环，for 循环的每个组件都有一个 O(N) 的大 O。我的想法是正确的还是这个函数可能有不同的 Big-O？

标签： pythonfor-loopbig-o

Answer 1

这个是 O(1)。这不是因为循环，而是因为逻辑。仔细查看范围值。Range 函数与单个参数一起使用时，会为您提供一个范围对象，其功能有点像列表 [0, ..., n]。对于那里的每个循环，每个 a、b 和 c 的第一个值将始终为 0。因此，您将始终遇到 a+b+c==0 中断。

我猜这是为了家庭作业？你总是可以尝试自己运行几次，看看输出是什么样子的。修改代码以执行以下操作可能会让您对函数内部发生的事情有一个不错的了解。

def sample_func(n):
    total = 0
    for a in range(n):
        for b in range(n - a):
            for c in range(n - b):
                total += 1
                if a + b + c == 0:
                    break
            if a + b == 0:
                break
        if a == 0:
            break
    print( total)
    return n + 1

for i in range(20):
    sample_func(i)