任何人都可以解釋大O與大歐米茄vs Big Theta？

Question

可能重複：
Big Theta Notation - what exactly does big Theta represent?

我的理解是在理論上，我想，但什麼我無法把握的三大應用。

在學校裏，我們總是用Big O來表示算法的複雜性。例如，泡泡排序爲O（n^2）。

現在閱讀了一些更多的理論後，我得到了大哦不是唯一的措施，至少有兩個有趣的。

但這裏是我的問題：

大O是上界，大歐米茄是下界和大西塔是兩者的混合。但是這在概念上意味着什麼？我明白圖表上的含義;我見過一百萬個這樣的例子。但是算法的複雜性意味着什麼？ 「上限」或「下限」如何與此混合？

我想我只是沒有得到它的應用。我知道如果乘以某個常數c，如果在某個值n_0 f（x）大於g（x）後，f（x）被認爲是O（g（x））。但是這實際上意味着什麼？爲什麼我們將f（x）乘以某個值c？地獄，我認爲與大O符號倍數無關緊要。

Answer 1

大O符號及其親屬，大的Theta，大的Omega，小的o和小的omega都是一些關於函數如何在極限點表現的方式（例如，當接近無限時，而且在接近0時等）而沒有多說其他功能。它們通常用於描述算法的運行空間和時間，但也可以在其他數學領域中看到漸近行爲。

半直觀的定義如下：

的函數g（x）被說成是O（F（X））如果 「從某一時刻」，G（x）是比C下* f（x），其中c是一些常數。其他定義相似，Theta要求g（x）在f（x）的兩個常數倍數之間，要求g（x）> c * f（x）的歐米茄，小版本要求這是對於所有這些常量都是如此。

但爲什麼有趣的說，例如，一個算法的運行時間爲O（n^2）？

這很有趣，主要是因爲在理論計算機科學中，我們最關心算法如何處理大輸入。這是事實，因爲對於小輸入，算法運行時間可能因實現，編譯，硬件以及其他在理論上分析算法時沒有意思的事情而大不相同。

然而，增長率通常取決於算法的性質，爲了改善它，您需要對您正試圖解決的問題有更深入的瞭解。例如，排序算法就是這種情況，您可以在O（n^2）中獲得一個簡單的算法（Bubble Sort），但爲了將其提高到O（n log n），您需要一個真正的新思路如合併排序或堆排序中引入的那樣。另一方面，如果你有一個運行在5n秒內的算法，而另一個運行在1000n秒內的算法（例如，對於n = 3，這是一個長時間的打哈欠和一個發射中斷之間的差異），當你達到n = 1000000000000時，規模的差異似乎不那麼重要。如果你的算法需要O（log n），你必須等待log（1000000000000）= 12秒，或許乘以某個常量，而不是幾乎317，098年，而不管常量有多大是，是一個完全不同的規模。

我希望這可以讓事情變得更清楚。祝你好運！