0

下面是我写的一些伪代码，给定一个数组 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
4

3 回答 3

5

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)。

于 2012-09-25T08:36:22.443 回答
1

是的。在最坏的情况下，您的算法是 O(n 2 )。

您的算法是 O(n 2 )，因为每个输入实例都需要时间复杂度 O(n 2 )。
您的算法是 Ω(1)，因为存在一个输入实例只需要时间复杂度 Ω(1)。

以下出现在Cormen、Leiserson、Rivest和Stein合着的算法简介的第 3 章“函数的增长”中。当我们说算法的运行时间（无修饰符）为 Ω(g(n)) 时，我们的意思是无论为每个 n 值选择什么大小为 n 的特定输入，该输入的运行时间为对于足够大的 n，至少有一个恒定的时间 g(n)。

给定一个输入，其中前两个元素的总和等于 k，这个算法在返回 true 之前只需要一次加法和一次比较。因此，该输入花费了恒定的时间复杂度，并使该算法的运行时间为Ω(1)。

无论输入是什么，该算法在返回值之前最多需要 n(n-1)/2 次加法和 n(n-1)/2 次比较。因此，该算法的运行时间为 O(n 2 )

总之，我们可以说该算法的运行时间介于 Ω(1) 和 O(n 2 ) 之间。我们也可以说这个算法的最坏情况运行是 Θ(n 2 )。

于 2012-09-25T08:27:24.817 回答
-2

你是对的，但让我解释一下：

这是因为第一个 for 循环运行了 n 次，而这个循环中的 for 循环也运行了 n 次。

实际上，第二个循环会运行(n-i-1)多次，但就复杂性而言，它将被视为n唯一。（根据phant0m的评论更新）

所以，在最坏的情况下，它会运行n * (n-i-1) * 1 * 1多次。这是O(n^2)。

在最好的情况下，它会运行1 * 1 * 1 * 1多次，O(1)即恒定。

于 2012-09-25T05:47:18.800 回答