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

[NOtWorThy (分子小於64)]

題目是說有個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
推 willow02:從右上角A[0,n]開始跟K比 若K<A[i,j]則往左一格
→ willow02:若A[i,j]<K 則往下一格
→ willow02:重複以上 直到找到等於K為止
→ NOtWorThy:那我那樣可以嗎>>
推 smalling:T(n)=3T(n/4)+1 原po作法應該可以 時間O(logn)
→ NOtWorThy:THX!!
→ ie925155:台大不考一樣的 做考古無用
→ polomoss:推樓上...
推 FRAXIS:這方法怎麼保證一定可以刪去1/4 (第二輪之後)