[理工] [資結]-複雜度

看板Grad-ProbAsk作者 (小澤)時間16年前 (2010/02/17 21:03), 編輯推噓3(303)
留言6則, 3人參與, 最新討論串5/5 (看更多)
State the definition of Θ(3^n) = ω(2^n) Then, prove or disprove the equality. -- ◤ ◥◤ ◥◤ ◥◤ ◥ Σ ◆ ◆ Σ ◆ ◆ Σ ◆ ◆ Σ ◆ ◆ ++++++ ++++++ ++++++++++++◥▇▆@ @▆▇◤ Ψ Ψ ▄▄▄ ▄▄▄ / \ ΓVISS -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.108.159

02/17 23:01, , 1F
disprove
02/17 23:01, 1F

02/18 10:52, , 2F
Why?
02/18 10:52, 2F

02/18 22:30, , 3F
我也覺得是錯的~但不會證~有人會嗎?
02/18 22:30, 3F

02/19 08:17, , 4F
要看他=是指啥 Θ(3^n) 必定Ω(3^n) 那就ω(2^n)
02/19 08:17, 4F

02/19 08:17, , 5F
右邊會包含左邊(我們一般討論複雜度的是這種等號)
02/19 08:17, 5F

02/19 08:18, , 6F
但是如果=是指全等 那很顯然是錯的
02/19 08:18, 6F
文章代碼(AID): #1BU-avrP (Grad-ProbAsk)
文章代碼(AID): #1BU-avrP (Grad-ProbAsk)