[资工] 交大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也不会比较慢，不是吗？