下面是我写的一些伪代码,给定一个数组 A 和一个整数值 k,如果 A 中有两个不同的整数之和为 k,则返回 true,否则返回 false。我正在尝试确定该算法的时间复杂度。
我猜这个算法在最坏情况下的复杂度是 O(n^2)。这是因为第一个 for 循环运行了 n 次,而这个循环中的 for 循环也运行了 n 次。if 语句进行一次比较,如果为真则返回一个值,这都是常数时间操作。最后的 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