确定算法的时间复杂度

Question

下面是我写的一些伪代码，给定一个数组A和一个整数值k，如果与k之和中有两个不同的整数，则返回true，否则返回false。我正试图确定这个算法的时间复杂度。

我猜这个算法在最坏的情况下的复杂度是O(n^2)。这是因为第一个for循环运行n次，该循环内的for循环也运行n次。if语句进行一次比较，如果为true，则返回一个值，这两个操作都是常量时间操作。最后的return语句也是一个常数时间操作。

我的猜测正确吗？我是新的算法和复杂性，所以请纠正我，如果我哪里出错了！

Algorithm ArraySum(A, n, k)
for (i=0, i<n, i++)
    for (j=i+1, j<n, j++)
        if (A[i]+A[j]=k)
            return true
return false

Answer 1

Azodious的推理是不正确的。内循环并不简单地运行n-1次。因此，您不应该使用（外部迭代）*（内部迭代）来计算复杂性。

要注意的重要一点是，内循环的运行时随外循环的每次迭代而变化。

这是正确的，第一次循环运行时，它将执行n-1迭代。但在那之后，迭代的数量总是减少一个：

null

请注意，您不能提供有意义的下限，因为算法可能在任何步骤后完成。这意味着算法的最佳情况是O(1)。