Big Theta表示法中常量的值

在Big Theta表示法中，常量c1和c2對於每個值n？都不同。Big Theta表示法中常量的值

定義：

Theta(g(n)) = {f(n): there exist c1 >= 0, c2 > 0 and n0 > 0 
        such that for all n >= n0, 
        0 <= c1, g(n) <= f(n) <= c2 * g(n)}

2012-09-08 sparth

這只是數學，不是很好所以。 – 2012-09-08 04:52:21

這可能會更好發佈在理論計算機科學StackExchange上：http://cstheory.stackexchange.com/ – Maz

我認爲常量是針對每個函數f的。如果存在'c1'，'c2'和'n0's.t，那麼函數f就在那個集合中。對於所有的n> = n0，'0 <= c1'，'g（n）<= f（n）<= c2 * g（n）'。 – Blender

c1和c2不適合的n每個值不同。如果他們是，他們將依賴於n，並不會是常數。

2012-09-08 04:57:20

如果存在三個函數n，n^2和n^3，並且對於函數n^2中的每個n值，我們有函數n和n^3以恆定的比例不同。我們稱之爲常數c1和c2？ – sparth

但是'n'和'n^3'沒有一個常數不同;對於任何常量'c'，'cn

是的，我得到的n和n^3是不同的常數。但是，我無法掌握你對常數的想法。你可以請更多的細節，也舉個例子嗎？ – sparth

Theta(g(n)) = {f(n): for all n >= n0, there exist c1 >= 0, c2 > 0 and n0 > 0 
       such that 0 <= c1, g(n) <= f(n) <= c2 * g(n)}

我不認爲你的定義中的量詞是正確的。它應該是

Theta(g(n)) = {f(n): there exist c1 >= 0, c2 > 0 and n0 > 0 
       such that for all n >= n0, c1 * g(n) <= f(n) <= c2 * g(n)}

2012-09-08 05:31:44

對不起，這是我的錯誤。現在應該修好了。 – Blender

回答