python - 算法运行时迭代for循环分析

Question

如果我有以下代码

def func(A,n):
    for i in A-1:
        for k in A-1:
            for l in A-1
                if A[i]+A[k]+A[l] = 0:
                    return True
                else:
                    return False

我如何分析该算法的运行时间？正如我所见，每个 for 循环都有 2 个单元，每个循环运行 n+1 次。然后 if 循环运行 3*n 次，有 3 个单元。然后每个返回都是一个，但是只有其中一个会运行，所以总的来说它相当于

T(n) = 2(n+1)+2(n+1)+2(n+1)+3(n)+1 = 9n+7

我的逻辑是正确的还是我遗漏了什么。运行时也可能因语言而异吗？

Answer 1

正如评论所说，现在的代码是 O(1)，因为每次通过一次后它都会退出 func。

如果您确实将返回更改为其他内容，例如设置变量，那么它将变为 O(n^3)。

为了解释如何获得该值，我将把问题简化为两个循环:

def func(A,n):
   for i in A-1:
      for k in A-1:
         # Do Something else

如果你想一下这是在做什么，对于我们遍历的 i 的每个值，我们将执行 A-1 次以通过 k 循环。

i=0, k=0
i=0, k=1
...
i=0, k = A-1

所以这会持续 A-1 或 n 周期。然后，

i=1, k=0
i=1, k=1
...
i=1, k=A-1

这也会持续 n 个周期。看到图案了吗？对于 i 的每个值，我们将迭代 n 次。现在，这将继续进行，直到我们用尽 i 的所有值，我们知道这也是 A-1 或 n 次。因此，此函数的运行时间将为 O(n^2)。

严格来说，最坏情况下的运行时 (big-O) 不会因编程语言而异。当然，每种编程语言的优化程度不同，执行时间长短也不同，但严格考虑算法周期，它们是相同的。