grimm-grimm https://blog.hatena.ne.jp/grimm-grimm/ grimm-grimmのうつ病克服日記 https://grimm-grimm.hatenadiary.org/ 分散アルゴリズム O(n^2)のメッセージ数がかかるアルゴリズムを紹介した。以下では、O(n log n) のアルゴリズムを紹介する。基本的なアイデアを示す。双方向リング上で考える。 ばつ印は、除外プロセスとする。それ以外は、始動プロセス。隣接したプロセス同士でプロセッサ番号を比較し、自分の番号が隣接したプロセッサ番号の中で、一番大きくないときに自分を除外プロセスへ移行する。このように、隣接したプロセスと自分のプロセスを除外していく。このようにすることで、少なくとも半分のプロセスへ減らせる。 以上は、双方向リング上で考えたが、これを短方向リング上で実現する。アルゴリズムを以下に示す。 アルゴリズム3 [待機状態… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fgrimm-grimm.hatenadiary.org%2Fentry%2F20110404%2F1301923557" title="４、リーダー選挙問題２ - grimm-grimmのうつ病克服日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/g/grimm-grimm/20110404/20110404225019.jpg Hatena Blog https://hatena.blog 2011-04-04 22:25:57 rich https://grimm-grimm.hatenadiary.org/entry/20110404/1301923557 1.0 100%