算法的渐近运行时间

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

输入：一组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），当且仅当在R中存在一个n0∈N且c> 0，这样对于所有的 n≥n0我们有 f（n）≤cg（n ）。并且我们还假设如果在R中有一个 n0∈N且c> 0，那么f是Ω（g），使得对于所有n≥n0，我们有 f（n）≥cg（n）。现在我知道该算法正在进行c * n（n-1）次迭代，产生T（n）= c * n^2 - c * n。对于n - 1次迭代，前3行执行O（1）乘以4行循环，即O（n）。第5行循环用于n-i迭代，它也是O（n）。内循环内容（第6-7行）的每一行需要（n-1）（ni）还是O（1）？为什么？唯一的变化是执行8.（d←t）多少次，但是它必须低于或等于O（n^2）。（n）= O（n^2），T（n）=Ω（n^2），并且T（n）=Θ（n^2））？预先感谢

来源

2011-02-23 Patrick88

计算次数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)。

来源

2011-02-23 18:36:41 IVlad

T(n)=c*n^2 - c*n大型n接近c*n^2，这是O(n^2)定义。

来源

2011-02-23 18:25:27 rmmh

感谢您的回复，但我对写一个完整证明的建议感兴趣？ – Patrick88 2011-02-23 18:27:00

对不起，但我不同意你在这里，我们只保证cf（n）的上界，例如对于一些常数c> 0。 – Patrick88 2011-02-23 19:21:43

@ Patrick88：实际上你在这里都有界限。请仔细看看欧米茄的定义。 c1 * n^2 <= c * n^2-c * n => c1 <= c-c/n;显然从你的c的一些n0开始，你可以得到c1。 QED – gorlum0 2011-02-23 19:55:36

如果您观察到两个for循环，则每个for循环都会给出一个O（n），因为每个循环都以线性方式递增/递减。因此，两个组合大致给出O（n^2）复杂度。大哦的全部重点是找到主要的术语 - 系数不重要。我强烈建议以适当的方式格式化您的伪代码，使其不含糊不清。在任何情况下，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）

因此，所有你需要的是找到其满意的答复约束。

来源

2011-02-23 18:39:02

算法的渐近运行时间

回答

相关问题