推 Purlas :很詳細!感謝回答 03/17 00:32
※ 引述《Purlas (皮拉斯)》之銘言：
: 1.
: n^2-2n=Ω(n^2）
: Ω對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n0 與 c > 0，
: 使得所有整數 n >= n0 都滿足 0 <= cg(n) <= f(n)，則 f(n) 屬於 Ω(g(n))。
: 這題我認為找不到C0跟n使之0成立，對嗎?
取 n0 = 4, C = 1/2
我們有 n ≧ 4
→ (1/2)n(n-4) ≧ 0
→ (1/2)(n^2) - 2n ≧ 0
→ n^2 - 2n ≧ (1/2)(n^2)
重點在於 C 沒有規定要大於等於 1 只要是正的就夠了
: 2.log^2(n)=ο(n^1/3)
: ο對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n0 與 c > 0，
: 使得所有整數 n >= n0 都滿足 0 <= f(n) < cg(n)，則 f(n) 屬於 ο(g(n))。
: 這一題我也找不到C0跟n0使之成立，對嗎?
: 如何證明?
: 還是其實有? 感謝解答!
首先有個事實: 對 N ≧ 32 = 2^6 有 N^6 < 2^N
這可由數歸證明 在此略去 (Hint: ((N+1)/N)^6 < 2)
由此我們有 (令 N = n^(1/6), 即 n = N^6 )
N^6 < 2^N
→ log N^6 < N (兩邊取對數)
→ log n < n^(1/6)
→ log^2 n < n^(1/3) (兩邊取平方)
以上在 N ≧ 32 即 n ≧ 32^6 時成立
因此 n0 = 32^6, C = 1 滿足條件 得證
(我假設你這是以 2 為底
不過如果是自然對數或常用對數只要前面的數歸改一下 後面 n0 對應的改動即可)
---
這種問題的思路都是反過來做
任意給個 C 然後試著推推看有沒有 N 符合條件
因此重點就在 C 的選擇
問題一如果你選了大於 1 的 C 就不容易找 N
問題二則是中間過程有點複雜所以沒辦法一眼看出 N 要多少
事實上問題二裡 上面的解法和我的思路正好是反過來的
我先任意定了 C = 1 然後倒著推回去 推到我要讓 N^6 < 2^N 成立
然後去找什麼時候它成立 發現 N ≧ 32 就行了這樣
(會取 32 上面也有寫了: 32 = 2^6 這樣初始條件比較好證明
不然根據軟體畫圖表示 N ≧ 30 就行了)
於是回頭倒著寫下來就是上面的解法
--
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.28.91