我真搞不清楚時間compexity

我明白，一個算法的時間T(n)可以通過O(g(n))被定義爲界：我真搞不清楚時間compexity

T(n) is O(g(n)) iff there is a c > 0, n0 > 0, such that for all n >= n0:

至多c * g(n)步驟大小n, A拍攝的每個輸入。 T(n)是大小爲n的所有輸入中最長的時間。

但是我不明白的是Ω(g(n))的定義。定義是對於一些輸入的大小爲n，A至少需要c * g(n)步驟。

但是，如果這是Ω的定義，那麼我不能找到任何algorthm的下限是相同的上限？例如，如果在最糟糕的情況下排序需要O(nlogn)，那麼我不能很容易地顯示Ω(nlogn)以及如何必須至少有一個壞的輸入的任何大小n將採取nlogn步驟？讓我們假設我們正在談論heapsort。我真的不知道我在這裏錯過了什麼，因爲每當我被教導一種新的算法時，某種方法的時間是Ɵ(g(n)) or O(g(n))，但沒有解釋爲什麼它是Ɵ or O。

我希望我說的話很清楚，如果不是的話就問一下你誤解了什麼。我真的需要清除這個混淆。謝謝。

來源

2012-04-13 shn

該死的複雜！ – FUD 2012-04-13 04:40:44

我一直在軟件行業工作了10年，唯一有過的是O符號... – Bill 2012-04-13 04:49:32

「對於大小爲n的某些輸入」的這一定義也適用於Big-O，如果我你說得對。這基本上意味着對於低數字n它可以高於/低於你的界限，通常假設一個點n_0，之後它總是正確的。然而，在學習的時候，你可能只需要其他的邊界，大O是最重要的一個，你會在整個人生中看到。 – jorey 2012-04-13 05:10:13

是我所熟悉的定義是，T（n）是Ω（G（N））如果由於某種n0，所有n>n0，T(n) >= g(n)*k一些k。如果它既是O（g（n））又是Ω（g（n）），則某事是Θ（n）。

來源

2012-04-13 05:03:48 trutheality

O是一個上限，這意味着我們知道一個算法，是O(n lg n)需要，漸近，頂多恆定倍，在最壞的情況下n lg n步驟。

Ω是一個下界，這意味着我們知道在最壞的情況下，Ω(n lg n)算法不可能漸近地採用步驟。

Ɵ是一個嚴密的約束：例如，如果一個算法是Ɵ(n lg n)那麼我們就知道這兩個，這既是O(n lg n)（這樣至少一樣快n lg n）和Ω(n lg n)（所以我們知道它的速度不能超過n lg n）。

您的論點存在缺陷的原因是您實際上假設您知道Ɵ(n lg n)，而不僅僅是O(n lg n)。

例如，我們知道有一個Ω(n lg n)一般約束比較排序。一旦我們爲mergesort證明了O(n lg n)，那麼意味着mergesort是Ɵ(n lg n)。請注意mergesort是也O(n^2)，因爲它的不慢比n^2。（人們通常不會這樣描述它，但正式符號的含義就是這樣。）

對於一些算法，我們不知道緊密的邊界;簡單計算模型中的一般3SUM problem已知爲Ω(n lg n)，因爲它可以用於執行排序，但我們只有Ɵ(n^2)算法。該問題的最佳算法在n lg n和n^2之間;我們可以說它是O(n^2)和Ω(n lg n)，但我們不知道Ɵ。

還有o(f)，這意味着嚴格小於f和ω(f)，這意味着嚴格大於f。

來源

2012-04-13 05:03:58 Dougal

對於Ω（你的答案中的第4行），你說「在最壞的情況下」，那麼爲什麼在最壞的情況下我不能證明堆排序可以取Ω（nlogn）呢？根據定義，難道我找不到任何大小爲n的輸入x會導致heapsort至少需要nlogn個步驟嗎？這樣heapsort然後是n（n lg n）。如果我理解你在說什麼，那麼heapsort不可能有任何大小爲n的輸入x，這會導致它受到Ω（nlogn）的限制？有沒有辦法知道我何時找不到Ω（g（n））？ – shn 2012-04-13 06:17:37

@shn通過使用關於計算樹的高度或熵的標準參數，您完全可以顯示堆排序是\ Omega（n lg n）。堆排序是\ Theta（n lg n），通過該參數加上它是O（n lg n）的參數。我不確定你下一個問題的含義，但是如果你知道o（n lg n），或者O（f）對於某些f Dougal 2012-04-13 13:58:22

我真搞不清楚時間compexity

回答

相關問題