A - Balanced Paths 解説 by maspy
解説 PDF では、weighted-union heuristic により時間計算量が \(O(N\log N)\) であると記述されています(理由説明なし)。 実際には、線形時間 \(\Theta(N)\) で動くので、指摘しておきます。\(\Theta(N\log N)\) が主張されているわけではないので誤りではないですが。
\(1\) 元からなるデータを \(N-1\) 回マージして、\(N\) 元のデータを作ります。
- 大きさ \(n\), \(m\) のデータを \(O(\min(n,m))\) 時間かけて、大きさ \(n+m\) のデータへとマージする場合:\(O(N\log N)\) 時間。
- 大きさ \(n\), \(m\) のデータを \(O(\min(n,m))\) 時間かけて、大きさ \(\max(n,m) + O(1)\) のデータへとマージする場合:\(O(N)\) 時間。
で、今回は、後者のパターンです。
前者の場合、ひとつひとつの要素が移動する回数を数えて \(O(N\log N)\) という計算量解析をしますが、後者の場合、ひとつの要素の移動(というより削除と見なすと良い?)は \(1\) 回ずつです。
投稿日時:
最終更新: