Re: [問題] approximation
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間12年前 (2012/04/03 22:22)推噓2(2推 0噓 1→)留言3則, 2人參與討論串1/2 (看更多)
※ 引述《wsx02 ()》之銘言：
: http://ppt.cc/_7PH
: 這是交大研究所的考題 不是作業0.0
: 這題我找了一些答案
: 想跟大大確認一下答案
: (6) O(|E| * (|E|+|V|)) 或
: O(|V| * (|E|+|V|))
: 不知道哪個是正確的..
照字面看 每次V點可選，運氣不好又重複選 O(無限大)
最普通的 每次V點可選，檢查邊需要E，總共要選V點 O(VVE)
強一點的 選過的點永不再選，檢查邊需要E，總共要選V點 O(VE)
最強的 如果一開始先把兩點之間多重的edge拼起來 O(VV)
不知道考官喜歡哪一種......
: (7) 1/2 或
: |E|/2
: 不知道應該填哪一個
E
運氣好的時候可以找到正解
運氣好是什麼時候呢？ 正解最大會是多少呢？
例如下面那題的完全二分圖 :p
: (8) 找到的是2n^2 可是不是很確定
: 謝謝
完全二分圖(X,Y)一定可以找到正解
抓一個點過去 ---> a. 與X同側: 邊數為零，不會增加邊，所以最後啥都沒做
b. 與Y同側: 因為是完全圖，一定會增加邊
所以答案就是 K(2n, 2n) 的邊數 2n * 2n = 4nn
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.125.83
※ 編輯: DJWS 來自: 61.230.125.83 (04/03 22:32)
推
04/04 11:50, , 1F
04/04 11:50, 1F
推
04/07 18:31, , 2F
04/07 18:31, 2F
→
04/07 18:37, , 3F
04/07 18:37, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
