CourseraにAlgorithms Part1という授業があり、これが非常に評判が良いので、会社で勉強会をしている。Week1にUnion Findというアルゴリズムが出てきて、その実装パターンがいくつかあった。それぞれ計算量が違うらしいのだけど、速度がどのように変化するか試したかったので、実装してパフォーマンス計測をしてみた。それぞれの実装の詳しい説明が知りたかったら、https://www.coursera.org/learn/algorithms-part1 を見ると良い。 Union Findとは何か 二つのノードを繋いでいき(Union)、あるノードとあるノードがつながっているか(Find or Connected)を判定するアルゴリズム。 例えば、union(1,6)、union(5,6)、union(2,7)、union(3,8)、union(4,9)、union(8,9
![Union Findアルゴリズムの様々な実装とパフォーマンス計測 - $shibayu36->blog;](https://cdn-ak-scissors.b.st-hatena.com/image/square/e7bee929a3c512149baac71256f5a33b594f0ac1/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fs%2Fshiba_yu36%2F20170212%2F20170212175011.jpg)