推 CSGD: 如果用min heap, find-min可以降到O(1), build可以降到O(n) 12/12 12:48
→ CSGD: 不過我是用nxn matrix, min另存, 這樣每次更新需檢查2n-1個e 12/12 12:51
→ CSGD: ntry 12/12 12:51
推 mathtsai: 1.建好n^2個f(x,y) -> O(n^2) 12/12 12:52
→ mathtsai: 2.用這n^2個元素建立heap -> O(n^2) 12/12 12:52
→ mathtsai: 3.m次操作 會更動m*(2n-1)個decrease-key -> O(mnlgn) 12/12 12:54
→ CSGD: 我nxn沒有建heap, 只有存matrix, 每次改值只在更動到的(2n-1 12/12 13:06
→ CSGD: )個entry找最小和目前的min比, 我自己推是O(mn), 還是哪裡想 12/12 13:06
→ CSGD: 錯了呢QQ 12/12 13:06
→ mathtsai: matrix一開始用完就丟進heap裡了 要改都在heap改 12/12 13:12
→ CSGD: 所以我沒有要建heap...只是2d array 12/12 13:16
→ mathtsai: C大 m次更動中有可能改到最小的元素 這樣要怎麼找min？ 12/12 13:35
推 CSGD: 對...那應該還是要用n個heap才對，感謝! 12/12 13:51
推 joywilliamjo: 我是寫建立min-heap欸，這樣找min都是O(1),n個就O(n 12/12 14:23
→ joywilliamjo: ),insert/delete也是O(nlgn) 12/12 14:23
推 asd3136396: 我的想法是先建出nxn的元素 12/12 14:41
→ asd3136396: 然後放進Fibonacci heap O(n^2) 12/12 14:41
→ asd3136396: 更改一次decrease-key O(2n-1) 12/12 14:41
→ asd3136396: 共m次O(mn) 12/12 14:41
→ asd3136396: total（n^2+mn) 12/12 14:41
→ asd3136396: 這樣想不知道有沒有錯 12/12 14:41
→ jimmylin1024: 感謝各位大大！ 12/12 15:02
→ jimmylin1024: a大用Fibonacci Heap時間複雜度沒錯。 原本我卡的點 12/12 15:02
→ jimmylin1024: 是在做decrease key之前要先search這個element ，會 12/12 15:02
→ jimmylin1024: 是O(n)，所以才轉而可慮用AVL。 12/12 15:02
→ jimmylin1024: 不過後來想到可以用hashmap 來記錄各個點的在heap 12/12 15:02
→ jimmylin1024: 中index 位置，這樣Fibonacci 的decrease key就可以 12/12 15:02
→ jimmylin1024: amortize O(1) 12/12 15:02
→ jimmylin1024: 整體time complexity 就會是O(n^2) 12/12 15:02
→ jimmylin1024: m更新的話就會是O(mn) 12/12 15:02
→ mathtsai: 喔喔 Fibonacci heap時間當然快(？ 12/12 23:12