推 a9101214: 大師 10/28 03:43
→ ZooseWu: 恩 我沒意識到n不是最大數 而是陣列數量 打錯了 10/28 13:08
※ 引述《ZooseWu (動物園 公告)》之銘言：
: 思路：
: 動態規劃基本題
: 判斷兩個節點有沒有都在arr裡面
: 有的話就把兩個child的可能性乘起來
: 另外宣告一個Set
: 可以讓判斷乘數有沒有在陣列中的時候不用再找整個陣列一次
: 因為Set的時間複雜度是O(1)
: 原本想說可以不用理會乘數跟被乘數交換的狀況
: 反正最終都會輪到
: 但是後來看了別人的解答後
: 發現我沒有考慮到數字很大的情況下
: n跟sqrt(n)會差很大
: 有加上這個判斷可以讓時間複雜度從O(n^2)降到O(n*sqrt(n))
這裡感覺有點怪
sqrt 和 n 應該沒關係 你要比的應該是 sqrt(max(arr))
舉個例子 [1,2,3,4,5,13,169], n = 7
更新 dp[169] 的時候還是要掃完整個 arr
時間上是有變好 但複雜度沒有變 或者是要加類似 min(n, sqrt(max(arr)))
之類的東西進去
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.148.59 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698396781.A.345.html