[理工] [DS]-台大考古題

看板Grad-ProbAsk作者 (分子小於64)時間14年前 (2010/02/25 00:11), 編輯推噓3(3推 0噓 6→)
留言9則, 6人參與, 最新討論串1/1
題目是說有個nxn矩陣 行由左到是是遞增 列由上到下也是遞增 求一個有效率的演算法來找一個k的位置 我是這樣想的 找矩陣最中間的那個數 M[n/2, n/2]跟k比 若k比較大,則k必不在左上的那個子矩陣裡 // n/2 x n/2 所以只要遞迴去找其他3塊子矩陣 所以T(n)=T(3n/4)+1 //還是T(n)=3T(n/3)+1 ??有點錯亂 這樣可以嗎 煩請高手解惑 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 219.70.226.250
推
02/25 00:15, , 1F
從右上角A[0,n]開始跟K比 若K<A[i,j]則往左一格
02/25 00:15, 1F
→
02/25 00:16, , 2F
若A[i,j]<K 則往下一格
02/25 00:16, 2F
→
02/25 00:16, , 3F
重複以上 直到找到等於K為止
02/25 00:16, 3F
→
02/25 00:22, , 4F
那我那樣可以嗎>>
02/25 00:22, 4F
推
02/25 00:54, , 5F
T(n)=3T(n/4)+1 原po作法應該可以 時間O(logn)
02/25 00:54, 5F
→
02/25 01:00, , 6F
THX!!
02/25 01:00, 6F
→
02/25 01:23, , 7F
台大不考一樣的 做考古無用
02/25 01:23, 7F
→
02/25 09:06, , 8F
推樓上...
02/25 09:06, 8F
推
02/25 10:56, , 9F
這方法怎麼保證一定可以刪去1/4 (第二輪之後)
02/25 10:56, 9F
‣ 更多 NOtWorThy 的文章
文章代碼(AID): #1BXK-YYF (Grad-ProbAsk)