算法分析运行次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 个单元，每个循环运行s n+1 次。 if 循环然后运行s 3*n 次，有 3 个单元。然后每个 return 是一个，但是只有其中一个会运行，所以总共会等于

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

我的逻辑是正确的还是我遗漏了什么。另外，运行时间会因语言而异吗？

Answer 1

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

如果您确实将 returns 更改为其他内容，例如设置变量，那么它将变为 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)。

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

算法分析运行次for循环迭代

Analysis of algorithm run time iterative for loops

python

arrays

algorithm

array-algorithms