以下 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？

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)

以下 Python 函数示例的大 O

Big O for the following Python function example

python

big-o

for-loop