算法的渐近运行时间

Question

我决定尝试做一个关于分析算法最坏可能运行时间的问题并获得一些练习。 由于我是初学者，我只需要帮助以正确的方式表达我的答案。 我在一本使用以下算法的书中遇到了这个问题：

输入：一组 n 点 (x1, y1), 。 。 。 , (xn, yn) 其中 n ≥ 2。 输出：最近一对点的平方距离。 ClosePoints

1. if n = 2 then return (x1 − x2)^2 + (y1 − y2)^2
2. else
3. d ← 0
4. for i ← 1 to n − 1 do
5.   for j ← i + 1 to n do
6.     t ← (xi − xj)^2 + (yi − yj)^2
7.     if t < d then
8.       d ← t
9. return d

我的问题是如何提供一个很好的证明 T(n) = O(n^2),T(n) = Ω(n^2) 和 T (n) = θ(n^2)？，其中T(n) 表示最坏的可能运行时间。 我知道我们说 f 是 O(g)， 当且仅当存在 n0 ∈ N 且 c > R 中的 0 使得对于所有 n ≥ n0 我们有 f(n) ≤ cg(n)。 如果有一个，我们也说 f 是 Ω(g) n0 ∈ N 且 c > R 中的 0 使得对于所有 n ≥ n0 我们有 f(n) ≥ cg(n)。

现在我知道该算法正在执行 c * n(n - 1) 次迭代，产生 T(n)=c*n^2 - c*n。 前 3 行执行 O(1) 次，第 4 行循环执行 n - 1 次迭代，即 O(n) 。第 5 行循环 n - i 次迭代，这也是 O(n) 。内循环内容的每一行 （第 6-7 行）需要 (n-1)(ni) 或只是 O(1)？为什么？唯一的变化是执行 8.(d ← t) 的次数，但它必须小于或等于O(n^2)。

那么，我应该如何写一个好的完整的证明 T(n) = O(n^2),T(n) = Ω(n^2) 和 T(n) = θ(n^2)？ 提前致谢

Answer 1

计算 t 更改其值的次数。由于更改 t 是执行的最内层操作，因此找出发生的次数可以让您了解整个算法的复杂性。

i = 1 => j runs n - 1 times (t changes value n - 1 times)
i = 2 => j runs n - 2 times
...
i = n - 1 => j runs 1 time

因此，t 变化的次数为 1 + 2 + ... + n - 1。该总和等于n(n - 1) / 2。这主要是0.5 * n^2。

现在只要找到合适的常数，就可以证明这是Ω(n^2), O(n^2), θ(n^2)。

Answer 2

对于大的 n，T(n)=c*n^2 - c*n 接近于 c*n^2，这是以下的定义O(n^2)。

Answer 3

如果观察两个 for 循环，每个 for 循环都会给出 O(n)，因为每个循环都以线性方式递增/递减。因此，两个循环组合起来的复杂度大致为 O(n^2)。 big-oh 的重点是找到主导项——系数并不重要。我强烈建议以正确的方式格式化您的伪代码，使其不含糊。无论如何，if 和 else 循环不会影响算法的复杂性。

让我们观察各种定义：

大哦

• f(n) 是 O(g(n)) 如果 f(n) 是
渐近“小于或等于”
g(n)

大欧米茄

• f(n) 是 Ω(g(n)) 如果 f(n) 是
渐近“大于或等于”
到 g(n)

大西塔

• f(n) 是 θ(g(n)) 如果 f(n) 是
渐近“等于”g(n)

因此您所需要做的就是找到满足答案的约束。