Re: [理工] [algo] 99中央 第5題

看板Grad-ProbAsk作者 (4Jay)時間15年前 (2011/01/08 23:33), 編輯推噓3(3推 0噓 8→)
留言11則, 5人參與, 最新討論串2/4 (看更多)
獻醜了，提供一個簡單的想法 就像C大推文中所說的，先sort可以有降低複雜度的效果 首先一樣用暴力法在 X 和 Y 集合中找到x 和 y，所需時間為θ(n^2) 因此就能夠知道z = k - x - y的值 用這個值在 Z 集合中做binary search看看能不能找到即可 每一次做binary search的時間複雜度為logn 因此最後時間複雜度為θ(n^2 log n) 有錯請指正 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.247.97
推
01/08 23:39, , 1F
跟我想的不完全一樣 不過應該對吧!
01/08 23:39, 1F
→
01/08 23:40, , 2F
如果我想的沒錯 n = |x|*|y| 吧
01/08 23:40, 2F
→
01/08 23:42, , 3F
可以說說看方法一起討論看看^^
01/08 23:42, 3F
→
01/08 23:42, , 4F
雖然題目沒要求 不過我也覺得只降log n有點少
01/08 23:42, 4F
→
01/08 23:43, , 5F
嚴格說來這樣要(|X|log|X|+|Y|log|Y|+|X||Y|)log|Z|時間吧？
01/08 23:43, 5F
→
01/08 23:43, , 6F
因為他沒說|X| = |Y| = |Z|
01/08 23:43, 6F
→
01/08 23:46, , 7F
嗯嗯 我是假設|X|=|Y|=|Z|=n 不過對結論應該沒影響
01/08 23:46, 7F
推
01/08 23:55, , 8F
我同意y大, 比較嚴謹些吧 :)
01/08 23:55, 8F
推
01/09 00:00, , 9F
!!我一直以為dp能解= = 想說能不能降到O(n^2)之類的
01/09 00:00, 9F
→
01/09 00:01, , 10F
XD 感恩
01/09 00:01, 10F
→
09/11 14:08, , 11F
!!我一直以為dp能解 https://daxiv.com
09/11 14:08, 11F
‣ 更多 tetragramm 的文章
文章代碼(AID): #1DA8F8um (Grad-ProbAsk)
‣ 更多 tetragramm 的文章
文章代碼(AID): #1DA8F8um (Grad-ProbAsk)