作者fish0835 (以无用为大用)
看板Grad-ProbAsk
标题Re: [理工] 97东华资结
时间Thu Apr 9 20:21:34 2009
※ 引述《InitialShuk (Shuk)》之铭言：
: X Y为两个sorted好的 含n element的array
: 请用O(logN)的algo 找出 X联集Y之中间值
: 目前只想到O(N) .....
假设X,Y是由小至大排好的array
steps:
1.把X,Y的中间值a,b拿来比较
2.不失其一般性的假设 a < b ，则将X的左半部与Y的右半部删去。
3.重复 1~2 直到找到中间值
time complexity:
每次皆删去一半的不可能之情况，所以时间函数为...
T(n) = T(n/2) + O(1)
= O(lg n) //n为X联集Y之长度
有错请各位大大更正罗^^
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.229.83.185
※ 编辑: fish0835 来自: 61.229.83.185 (04/09 20:23)