如何計算不同符號的「n」大O，Omega，Litle O，Litle Omega和Theta符號

Question

我正在學習算法，但找到Time Complexity的計算對我來說並不那麼容易，它很難記住何時使用log n，n log n，n^2，n^3，2n等，我的疑惑是如何在計算複雜度時考慮這些輸入函數，是他們計算複雜度的具體方法，就像使用爲了循環，總是需要這麼多的複雜性，等等......？

Answer 1

的log（n）：當您使用遞歸和樹生成使用的log（n）。 我的意思是在鴻溝和征服當你潛水的問題爲2半區其實你正在生成遞歸樹。

它的複雜性是日誌（n），爲什麼？因爲它本質上是一棵二叉樹，對於二叉樹，我們使用日誌（Base2）（n）。

試試自己：假設n = 4（元素）所以log（base2）（4）= 2，你把它分成相等的一半。

nLog（n）：記住Log（n）它是除法直到單個元素。之後，你開始合併排序元素稱取班輪時間

換句話說元素的合併具有複雜「N」所以總的複雜性將是N（合併）+的log（n）（除）終於成爲nLog（n）。

N^2： 當你看到一個問題是，在兩個嵌套循環解決複雜性，然後是N^2。即他們在2個循環中計算的矩陣/ 2-D數組。外環內有一個環。

n^3：哦3-D數組，這是3個嵌套循環。循環內循環內循環。

2n：謝謝你沒有忘記用這個「n」寫下「2」，否則我忘了解釋這一點。

因此「2」在這裏與「n」是不變的只是忽略它。爲什麼？因爲如果你通過AIR去其他城市旅行。您只會計算飛行時間，而不是到達AIR端口所消耗的時間。我的意思是這是輕微的，我們刪除常量。

和「N」只記得這個詞「線性」即BIG-O（N）是線性的複雜性。令人遺憾的是，我發現沒有算法可以在線性時間對元素進行排序。即只在一個循環中（單個數組遍歷）。

事情要記住：

標稱時間：線性時間，複雜性大O（n）的

多項式時間：不是線性的時間，複雜性大O [日誌（N ），nlog（n），n^2，n^3，n^4，n^5）。

指數時間： 2^N，n次方，即這一問題在指數時間會解決即，N ^力（N）（這是很壞很壞的壞，不叫算法）[大的

Answer 2

關於如何粗略計算Big O及其兄弟姐妹的複雜性有很多鏈接，但沒有真正的公式。

但是，有一些指導原則可幫助您計算複雜性，如下所示。我建議您查看許多不同的程序和數據結構，以幫助您熟悉該模式，並只需學習，學習，學習，直至您找到它！有一種模式，你會看到它越多，你研究它。

來源：http://www.dreamincode.net/forums/topic/125427-determining-big-o-notation/

1. 嵌套循環相乘。
2. 添加順序循環。
3. 只保留最大的術語，其他所有術語都被丟棄。
4. 常量被丟棄。
5. 條件檢查是恆定的（即1）。