大O表示法的預期語法

是否存在有限數量的基本O符號，考慮到您是將它們「蒸餾」到它們最重要的部分？大O表示法的預期語法

爲O（n^2）：

爲O（n）：

O（1）：（N！）

O（log n）的對數

ö階乘

O（na）多項式

或者您是否希望計算出變量，例如O（n^4）等......並且如果那麼，這是唯一的例外嗎？ X一個的力量？

來源

2012-02-02 SirYakalot

維基百科文章包括[正式定義]（http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition）。這並不難看。 – Nemo 2012-02-02 17:41:39

一般而言，您將Big-O符號（以及Big-Theta和Big-Omega相關的Bachman-Landau符號）提煉爲增長最快的N項的運算。這樣，在刪除/簡化較小術語（N + N == ø（N ））和術語（ø（4N ）==的nonvariable係數ø（N ）），但不權力或指數鹼基（ø（3 ^4N）== Ô（3 ^ñ））。你也不會去掉可變係數;因此，如果複雜度是多項式（N的冪）或指數（基數的N次冪），那麼通常只能看到Big-Oh符號中的數字。NlogN是NlogN，NOT是否N或N.

最常見的Big-Oh符號與您展示的很相似，但增加了NlogN（非常常見）。然而，如果您要區分相同一般複雜度的兩種算法，則可以添加較少的術語和/或係數以表示相對差異; （N）算法與其他指令進行比較時，可以描述爲線性執行但具有另一指令的算法的算法可以被描述爲（012）。但是，單獨採用這兩種算法都是線性的（O（N））。

某些Big-O符號不是代數的，可能涉及多個變量，以最簡單的一般形式表示。例如，計數排序的複雜性爲：其中N是列表中元素的數量，M是這些元素的範圍。在特定情況下，通常可以通過以N爲單位定義M並因此減少到單個變量（如果所討論的列表是前N個正方形，M = N -1），但在一般情況下，兩個變量都是獨立的和重要的BucketSort的複雜性正式爲O（N），但實際上更像O（NlogM）其中M是N個元素列表的最大值。M通常被認爲是微不足道的，但這取決於你通常排序的值（排序5個值在數十億中需要更多的循環來比較每個10的冪，而不是通過列表的遍歷來將它們放入桶中）以及使用的基數（RadixSort是基數爲2的BucketSort;同樣，排序值較大的值將需要比遍歷更多的循環）。

來源

2012-02-02 17:34:07 KeithS

Big-O符號是一種提供函數限制行爲上限的方法。其功能形式沒有限制。但是，有一些約定，如Wikipedia所解釋的：

在典型的用法中，O符號的形式定義不是直接使用;而，對於函數f O符號（x）由下面的簡化規則導出：

若f（x）是的幾個術語的總和，該具有最大生長速率被保持，並且所有其他省略。

如果f（x）是幾個因素的乘積，則省略任何常數（產品中不依賴於x的項）。

當然，還有一些功能性表現形式更頻繁地出現在其他人身上。一些常見的課程列出了here。

來源

2012-02-02 17:34:55 NPE

不，不同的O類的數量不是有限的。正如你已經提到的O（n^x）爲每個x描述了一個不同的集合。這不是唯一的「例外」。對於每個x，O（x^n）也是一個不同的集合。同樣地，O（n^n），O（n^n^n），O（n^n^n^n）等都是不同的集合（並且當然，您可以繼續無限）。

來源

2012-02-02 17:37:55 sepp2k

+1，但我也會在你的答案中加入由任意小事例產生的集合（用指數）;如：N * logN或N * 2^N或N * log^2 N等 – 2012-02-03 14:50:11

通常，將表達式拆分爲產品總和，保留最大的項，並用常數除以儘可能簡化。

例如：

N（2N + 3log（N））=> 2N^2 + 3nlog（N）=> 2N^2 => N^2

第（n + 1）（2nlog （n）+ n）=> 2n^2log（n）+ n^2 + 2nlog（n）+ n => 2n^2log（n）=> n^2log（n）

來源

2012-02-02 17:41:22 Retief

大O表示法的預期語法

回答

相關問題