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

[christianSK (AG)]

※ 引述《tetragramm (4Jay)》之銘言：
: 獻醜了，提供一個簡單的想法
: 就像C大推文中所說的，先sort可以有降低複雜度的效果
: 首先一樣用暴力法在 X 和 Y 集合中找到x 和 y，所需時間為θ(n^2)
: 因此就能夠知道z = k - x - y的值
: 用這個值在 Z 集合中做binary search看看能不能找到即可
: 每一次做binary search的時間複雜度為logn
: 因此最後時間複雜度為θ(n^2 log n)
: 有錯請指正
t大要求的話 我就獻醜了 :)

正如我前面推文說的 這是ACM來的

為什麼我知道呢?  因為這是我去年某堂課的hw (不過我不是中央的)

所以這方法其實也是老師上課提到的

要找 x,y,z, 使得 x + y + z = k  等同於找 x,y,z 使得 x + y = k - z

我只需要去比較 x + y , k - z 兩個list看是否有相同元素就可以了

(i)     constrcut 這兩個list  θ(|X|*|Y|) ,  θ(|Z|)

(ii)    對這兩個list做 q-sort θ(|X|*|Y|*log(|X||Y|)) ,  θ(|Z|*log(|Z|))

(iii)   最後就是比較, 用Binary search來做, 我想應該是

        θ( log ( |X|*|Y| ) * |Z| )



       ( 請允許我假設|Z| < |X|*|Y| XD" )

希望我想的沒錯~

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.243.147.23
推 aoqq12:!!!多謝解答
→ christianSK::)
推 tetragramm:請問為什麼(iii)的時間複雜度是那樣@@? 看不太懂QQ
因為我寫錯了XD" 感謝提醒

應該是這樣沒錯吧 我想~
※ 編輯: christianSK     來自: 111.243.147.23       (01/09 00:16)
→ christianSK:然後 (i) (ii) (iii) 取大的就是了吧
推 tetragramm:可是(ii)中的|X||Y|log(|X||Y|)比(iii)還大吧
→ christianSK:對阿 所以(ii) 決定這個algo的複雜度不是嘛
推 tetragramm:那不就跟我的時間複雜度一樣了嗎XD 應該不是|X||Y|吧
→ christianSK:我沒有說我的algo比較好阿@@"
推 tetragramm:喔喔 誤會 我以為你這個是θ(|X|*|Y|)的演算法囧
→ christianSK:有排序就不可能是 |X|*|Y|吧
→ tetragramm:嗯阿所以我剛剛一直在想我是不是哪裡想錯了XD"
→ christianSK:真不好意思 讓你誤會了m(_ _)m
推 tetragramm:哪裡~ 能討論不同的想法很有趣^^ 謝謝分享!
→ christianSK:真的滿有趣的 也可以找出一些盲點 :)
→ sneak: 嗯阿所以我剛剛一直在想 https://daxiv.com