算法的漸近運行時間

我已經決定嘗試做一個關於分析算法的最壞可能運行時間並獲得一些練習的問題。由於我是初學者，我只需要幫助以正確的方式表達我的答案。我在一本使用以下算法的書中提到了這個問題：算法的漸近運行時間

輸入：一組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

算法的漸近運行時間

回答

相關問題