兎と亀のアルゴリズムをふと考えてみた

リストの循環チェックアルゴリズムといえば、兎と亀のアルゴリズムが有名だけど、ふと疑問がわいたのでさらっと検証してみた話。時間も労力もかけたエントリではないけど、まぁいいかと。

兎と亀のアルゴリズムというのは、リスト構造を２つずつ辿るポインタ(兎)と、１つずつ辿るポインタ(亀)を用意して、兎が亀に追いつけば、そのリストは循環していると判断できるというアルゴリズム。

その話から最初に考えた擬似コードが下。兎が２つ進む間にちゃんと亀に追いついてるかどうかをチェックしている。

bool check(List *listp){
  List *turtlep = listp;
  List *rabitp = listp;

  while(1){
    turtlep = turtlep->next();
    rabitp = rabitp->next();
    if(rabitp == turtlep) return true;
    rabitp = rabitp->next();
    if(rabitp == turtlep) return true;
    if(rabitp == listp.end()) return false;
  }
}

しかし、このコードはあまり綺麗じゃない。で、よく書かれるコードは下の方なのかなーと思う。

bool check(List *listp){
  List *turtlep = listp;
  List *rabitp = listp;

  while(1){
    rabitp = rabitp->next()->next();
    turtlep = turtlep->next();
    if(rabitp == listp.end()) return false;
    if(rabitp == turtlep) return true;
  }
}

ただ、こちらの場合だと、兎が亀を追い越し続ける場合があるんじゃね？と思ってしまった。

そこで実際に何ターン(ループの実行回数)で兎が亀と同じ地点に立つかを計算してみる。亀がリストの循環ループ部分に入った時に、兎が循環ループのk番目の地点にいるとする。

${ \displaystyle Rabbit_0 = k, \ Turtle_0 = 0 }$

すると、それからtターン経過した時の兎と亀の位置はそれぞれ

${ \displaystyle Rabbit_t = 2t + k, \ Turtle_t = t }$

従って、兎と亀の距離は、 ${ D_t = t + k}$ となるから、循環ループを構成するノード数をmとすると、 ${ D_t }$ がmの倍数になれば追いつく計算である。つまり、循環部分で兎が亀に追いつくまでに必要なターン数はたかだかmのため、循環ループにたどり着くまでのノード数も考えると、最終的な計算量としては、O(n)で良いことがわかる。(nはノード数)

周期の一致とかを考えると最小公倍数かなぁとか一瞬考えてしまい、結構時間がかかることもある？とか思ってしまったけど、ちょっと考えてみるとなんか普通の答えで拍子抜けした話でした。