1
這是麻省理工學院OpenCourse 介紹的分配算法上漸近記法一個問題：
對於每一個下面的語句，決定是否總是如此，從來沒有真正，或有時真正漸近非負函數˚F和克。如果是總是如此或從未真正，解釋原因。如果是有時真，舉個例子，這就是它真正的，一個是它是假的。漸近記法
f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) (both are Big-O notes)
我認爲這是從來沒有真正。這是我的證明：
f(n) ≠ O(g(n))
=> f(n) = w(g(n)) (little-omega note)
=> g(n) = o(f(n)) (little-o note)
=> g(n) = O(f(n)) (big-O note)
結果與g(n) ≠ O(f(n)) (Big-O note)矛盾。同樣，
g(n) ≠ O(f(n))
=> g(n) = w(f(n)) (little-omega note)
=> f(n) = o(g(n)) (little-o note)
=> f(n) = O(g(n)) (big-O note)
它與f(n) ≠ O(g(n)) (Big-O note)矛盾。
解決方案說，這是有時真：
For f(n) = 1 and g(n) = ||n*sin(n)|| it is true,
while for any f(n) = O(g(n)), e.g. f(n) = g(n) = 1, it is not true.
我在哪裏，我證明什麼錯呢？另外，我無法理解解決方案。 ||n*sin(n)||看起來像向量規範給我。
假設||ñ罪（N）||應該閱讀| n sin（n）|並參考實數的絕對值（當然，這是R^1上的向量範數），反例是有意義的。本來可以選擇n *（1 +（ - 1）^ n）= 0，0，2，0，4，0，6 ......代替。 – tiwo 2012-07-21 20:11:38
一個教學旁註：也許你想要f = O（g）是一組函數的偏序，因爲它對於實數f，g感覺非常類似f≤g。 – tiwo 2012-07-21 20:19:14