作者polomoss (小泽)
看板Grad-ProbAsk
标题[理工] [资结]-Union-Find
时间Fri Dec 18 11:25:57 2009
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
1F：推 FRAXIS:O(n + m) 12/18 12:32