确定算法的时间复杂度

Question

下面是我写的一些伪代码,给定一个数组A和一个整数值k,如果A中有两个不同的整数,则返回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时间.因此,您不应该使用(outer iterations)*(inner iterations)计算复杂性.

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

这是正确的,第一次循环运行时,它会进行n-1迭代.但在那之后,迭代量总是减少一个:

• n - 1
• n - 2
• n - 3
• ...
• 2
• 1

我们可以使用高斯的技巧(第二个公式)来总结这个系列n(n-1)/2 = (n² - n)/2.这是在最坏的情况下比较总共运行的次数.

从这一点来看,我们可以看到界限不能比任何更严格O(n²).如您所见,没有必要猜测.

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