[理工] [資結]-Union-Find

[polomoss (小澤)]

If both weighting rule and collapsing rule are applied, what is the

time required for a sequence of n-1 Unions and m Finds


我的解法是

Union : O(1)    ,  n-1 個 : O(n)

Find : O(log*n) ,   m  個 : O(m)


答案: O(n+m)


這樣對嗎~? 還是只要寫O(n)?

--
┌這篇文章讓您覺得？─────────────────────────────┐
│                                                                            │
│    一"一     \  /    >\\\<    ╯ ╰    ∩ ∩    ▁ ▁   ＞＿＜    ㄧ ㄧ+   │
│      皿               ε       □        ▽    ▇Δ ▇   ╰╯        ╯    │
│     北七     亂喔     害羞     莎笅     爽啦     哭爸     ＸＤ     科科    │
└──────────────────────────────────────┘

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.116.14.2
推 FRAXIS:O(n + m)