Re: [理工] [資結]-時間複雜度

看板Grad-ProbAsk作者 (拋磚引玉)時間15年前 (2009/07/22 09:27), 編輯推噓1(1推 0噓 1→)
留言2則, 2人參與, 最新討論串2/38 (看更多)
※ 引述《SmallFoxChiC (小狐狸)》之銘言： log3 n 跟 nlogn 的複雜度是誰比較大呢
→
07/21 23:12,
洪捷書上兩題都是寫說前者較大但沒寫說為什麼
07/21 23:12
推
07/21 23:39,
我發現一樓推文沒注意到括號，怪不得後面的會變大得多
07/21 23:39
→
07/21 23:40,
這題不用取log 直接把前面的換成 3^logn 這樣的話
07/21 23:40
→
07/21 23:41,
前面是指數 後面是多項式 所以前面大 流程應該是這樣
07/21 23:41
→
07/22 00:21,
樓上這樣判斷會有問題，若題目改成 n^(log2)，若轉成
07/22 00:21
→
07/22 00:22,
2^(logn)，會以為是指數取向，但實際上那個等於 n
07/22 00:22
這樣呢？ lg3 lg3-1 lg3-2 n lg3 n lg3 (lg3-1) n lim -------- = lim ----------- = lim ------------------- n->∞ nlgn lgn + 1 1 / n lg3-1 = lg3 (lg3-1) lim n = ∞ lg3 ∴ nlgn = O (n ) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.93.39
推
07/22 23:33, , 1F
上下先同除n 再用羅必達會比較方便些
07/22 23:33, 1F
→
07/23 00:19, , 2F
謝謝 沒想到
07/23 00:19, 2F
‣ 更多 nowar100 的文章
文章代碼(AID): #1APcha-d (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 2 之 38 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共38篇)
‣ 更多 nowar100 的文章
文章代碼(AID): #1APcha-d (Grad-ProbAsk)