algorithm - 确定算法的时间复杂度

Question

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

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

我的猜测正确吗？我对算法和复杂性不熟悉，所以如果我有任何错误，请纠正我!

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 次。因此，您不应使用 (outer iterations)*(inner iterations) 来计算复杂度。

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

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

• n - 1
• n - 2
• n - 3
• …
• 2
• 1

我们可以使用Gauss' trick (second formula)对这个级数求和得到 n(n-1)/2 = (n² - n)/2。这是比较在最坏情况下总共运行的次数。

由此，我们可以看出边界不能变得比O(n²) 更紧。如您所见，无需猜测。

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