※ 引述《lovepy (sam)》之銘言：
: 但是我覺得這裡有點怪怪的
: 況且這只是算出n趨近於無窮大會成立
: 好像和存在有個n0的大於n會成立並不是若且唯若的關係
: 後者可以推至前者
: 但反向感覺不一定成立
: 這樣證好像不太完全
: 不過我自己也沒有辦法證明到底lg(n^n)是不是lg(n!)的下界
: 不知板上是否有人能為我解惑呢?
: 或是有甚麼比較好的方法?
: 謝謝
原來的定義是
"f(n) = Ω(g(n))" := 存在 n0 > 0, c > 0 使得當 n > n0 有 c*g(n) ≦ f(n)
用極限作法證得的是
g(n)
lim ---- = 1
n→∞ f(n)
依照極限的意義 它等於這樣一句話
對任意正數 ε > 0 存在正數 δ > 0
| g(n) |
使得當 n > δ 有 | ---- - 1 | < ε
| f(n) |
(回去回想基本微積分裡面極限的ε-δ定義)
從這裡我們可以知道的是
當 n > δ 時 我們有 g(n)/f(n) < 1+ε 即 (1/(1+ε))g(n) < f(n)
也就是當我們給定一個 ε 時 由極限定義我們找得到 δ
這個 δ 正提供了我們要的 n0 這時的 c 就能取 1/(1+ε)
這證明了極限方法是可行的
其實這個極限成立不只可以成立Ω 也可以成立Big-O 所以連Θ都成立
Big-O 的證明只需要把不等式取另外一個方向就好 這時 c 會是 1/(1-ε)
--
1985/01/12 三嶋鳴海 1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町
つぐみ 歡迎來到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬
チサト 1998/06/18 守野くるみ 打越鋼太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遙
2002/12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 ∞與∫的世界 2011/04/02 茜崎空
啟動 2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞 2019/04/01~07 某大學合宿
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.135