2008年8月21日 星期四

突破演算法

上午起床時,在還在神遊的狀態中,突然一個想法將這幾天想破腦的問題解決。

題目是這樣的,在許多集合中,找出若干元素可以匹配最多集合的組合。

一開始就知道用暴力解的複雜度了,是 big O(nn),沒錯是很可能算不出來的複雜度,做了一個簡單的範例,然後跑了兩天,還是跑不出結果。

而今天則想到,已知集合的總數,若消去最少的元素,則消去最少的集合,故得到最大的集合總數,照著這個邏輯只要 big O(n) 的複雜度,真是給他差很多,實做後運算的時間是秒殺,最大的運算量也不到 20 秒,真是令人高興的一件事。

沒有留言: