[資工] 交大103考古 請教數題
作者: qoojordon (穎川琦) 2014-09-29 21:27:54
請教數題交大103年的考古 , 我把題目篩選 , 裁成兩張圖片 , 問題詳述於內文
![]()
Algo+OS
![]()
數學
103 [Algo] : 以下自己都有一套說法 , 可是不太有把握 , 希望能互相討論
11a
我的答案 : false
all-pair shortedt path 演算法我只認識 Floyd-Warshall 和 Johnson ,
前者複雜度 n^3 , 後者 VE+V^2logV , 如果是sparse matrix的話後者表現
的確實比較好 , 是否有其他更有說服力的說法 ?
Algo+OS
數學103 [Algo] : 以下自己都有一套說法 , 可是不太有把握 , 希望能互相討論
11a
我的答案 : false
all-pair shortedt path 演算法我只認識 Floyd-Warshall 和 Johnson ,
前者複雜度 n^3 , 後者 VE+V^2logV , 如果是sparse matrix的話後者表現
的確實比較好 , 是否有其他更有說服力的說法 ?
作者: j897495 (咪咪) 2014-09-29 21:35:00
好快就在寫題目了XD
作者: qoojordon (穎川琦) 2014-09-29 21:39:00
QQ 大四畢業那年沒寫考古題就去考根本當砲灰
作者: A4P8T6X9 (殘廢的名偵探) 2014-09-29 22:59:00
OS, 4 from first to 5120thMATH 1 要投影到二維，所以會用到。MATH 4C 可以套MATH 9C他的思路是假設存在一個完美的正整數對應到(0,1)那麼我可以找到一個實數，其跟對應的每一個都不一樣。找法就是如果第i個對應的第j個是4，那麼這個數的第j個就設成5，否則就設成4，則這個絕對不會被對應到。algo 應該沒問題
作者: FRAXIS (喔喔) 2014-09-30 03:12:00
就算是dense graph，Johnson也不會比較慢，不是嗎？