我坐在這裏，在一個有關海量數據集的算法的課程中，使用Little-Oh符號讓我感到困惑，儘管我很完全有信心與大哦。小哦註釋細節，CS作業，不包括實際任務
我不想要一個解決方案的任務，因此我不會介紹它。相反，我的問題是我如何解釋時間複雜度o（log n）？
我從定義中知道，算法A必須比o（log n）漸近地慢，但我不確定這是否意味着算法必須在恆定時間內運行，還是仍然允許在某些條件下爲log n，使得c = 1或者如果它確實是log（n-1）。
說的算法具有○運行時間（log n）的但事實上確實兩次迭代，因此C = 2，但2 *日誌N仍然O（log n）的，很當我說這不適合Little-Oh時，我是對的嗎？
任何幫助是極大的讚賞，如果嚴格需要澄清，我將提供轉讓
要說f是f = o(g) '小-OH-的G' 是指該商數
|f(x)/g(x)|
接近0作爲x接近無窮大。請參考o(log n)的示例，該類包含log x/log (log x),sqrt(log x)等多種功能，因此o(log x)絕對不意味着O(1)。在另一方面，log (x/2) = log x - log 2，所以
log (x/2)/log x = 1 - log 2/log x -> 1
和log (x/2)不在類o(log x)。
這個定義不正確，'f（ n）= n *（1 +（1-exp（-n））* cos n）'在'O（n）\ Theta（n）'中，但不在'o（n）'中。 – 2012-02-19 16:02:37
拿了點。已刪除評論。不過，至少可以添加一個鏈接到另一個定義，這在某些情況下可能更有用：http://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation – Patrick87 2012-02-20 14:25:37
對於小哦，F（X）沒有比G（X）對於所有x小。只有在x的某個值後才能變小。 （對於你的問題，但它仍然允許日誌N在某些條件下。）
例如：
let f(x) = 5000x and g(x) = x^2
F（X）/ G（X）爲x接近無窮大是0，因此f （x）是g（x）的小數。然而，在x = 1時，f（x）大於g（x）。只有當x變得大於5000時，g（x）纔會大於f（x）。
真的很少告訴我們g（x）總是以比f（x）更快的速度增長。例如，看起來多少F（X）X = 1和x = 2間增長：
f(1) = 5000
f(2) = 10000 - f(x) became twice as big
現在看G（X）上以相同的間隔：
g(1) = 1
g(2) = 4 - g(x) became four times bigger
該速率將會增加甚至更大的x值。現在，由於g（x）以更快的速率增加，並且因爲我們將x取爲無窮大，所以在某個點它將變得大於f（x）。但這不是小關係所關心的，而是關於變化的速度。
嗯，爲什麼'[o-notation]'標籤是'[big-o]'的同義詞？對不起，我的意思並不是因爲我沒有閱讀第一行就重新出現...... – 2012-02-19 09:55:27
你說得對，我刪除了[big-o]標籤 – Casper 2012-02-19 09:59:03