[理工] 102成大程設

看板Grad-ProbAsk作者 (一樣的午後時光)時間4年前 (2020/02/09 22:01), 4年前編輯推噓3(3推 0噓 9→)
留言12則, 5人參與, 4年前最新討論串1/1
想請問這一題 https://i.imgur.com/SbLsXdQ.jpg
這一題題目不太明白在敘述什麼? 還有圈起來的符號(下標)是指什麼意思呢? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.76.143 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1581256881.A.D3C.html
推
02/09 22:04, 4年前 , 1F
請看演算法 np那章
02/09 22:04, 1F
→
02/09 22:06, 4年前 , 2F
啊 當兵完 演算法都忘光了 而且我演算法也讀一點點而已
02/09 22:06, 2F
→
02/09 22:06, 4年前 , 3F
好 我再去研究一下演算法 謝謝大大
02/09 22:06, 3F
→
02/09 22:14, 4年前 , 4F
剛剛去翻了一下NP-complete那章
02/09 22:14, 4F
→
02/09 22:15, 4年前 , 5F
想請問看完那一章 就可以明白這一題的觀念嗎?
02/09 22:15, 5F
→
02/09 22:15, 4年前 , 6F
np那一章在後半段 這題在資結第一章 所以我先略過嗎?
02/09 22:15, 6F
推
02/09 22:18, 4年前 , 7F
圈起來的那個符號可以想成想成P1的難度小於等於P2
02/09 22:18, 7F
→
02/09 22:18, 4年前 , 8F
又P2屬於p 因此P1也屬於p
02/09 22:18, 8F
請問一下~ 為什麼知道P2屬於p呢? ※ 編輯: oao521 (118.166.76.143 臺灣), 02/09/2020 22:22:54
推
02/09 22:28, 4年前 , 9F
因為對lglgn取lg得lglgn*lglglgn<lgn 因此lglgn屬
02/09 22:28, 9F
→
02/09 22:28, 4年前 , 10F
於多項式等級
02/09 22:28, 10F
明白了 原來是從定義得知 感謝指點 ※ 編輯: oao521 (118.166.76.143 臺灣), 02/10/2020 00:20:07
→
02/09 23:31, 4年前 , 11F
是 再加上一點時間複雜度的概念就會懂了
02/09 23:31, 11F
OK 我在研究一下 有問題再問你們~~ 乾蝦 ※ 編輯: oao521 (118.166.76.143 臺灣), 02/10/2020 00:21:05
→
02/10 10:32, 4年前 , 12F
p1可以使用polynomial time的演算法reduce到p2
02/10 10:32, 12F
https://i.imgur.com/5XWqwiq.jpg
請問是因為橘色畫線部分，所以p1可以使用polynomial time的演算法reduce到p2? ※ 編輯: oao521 (180.217.145.212 臺灣), 02/10/2020 10:48:32 ※ 編輯: oao521 (180.217.145.212 臺灣), 02/10/2020 10:50:23
‣ 更多 oao521 的文章
文章代碼(AID): #1UG12nqy (Grad-ProbAsk)