2

リンク リストのフロイド ループ検出アルゴリズムでは、通常、低速ポインターを 1 単位、高速ポインターを 2 単位ずつインクリメントします。低速ポインターと高速ポインターをインクリメントするために使用できる他の値は何ですか?また、アルゴリズムの複雑さをどのように変更しますか?

4

3 に答える 3

1

速度やループのサイズに関係なく、2 つのポインターは常に一致します。

次の値を使用します。

  • aand b: 各反復で各ポインターが実行するステップ数。
  • m: ループ内のノード数。

反復後i、2 つのポインターはステップaiを実行しbiます。iが十分に大きく、両方のポインターがループ内にある場合、それらは同じノードになります。

ai = bi (mod m)

これは次と同じです:

(a-b)i = 0 (mod m)

iこれは、 の値が の倍数でありm、十分に大きい場合に当てはまります。このような値は常に存在するため、ポインターは常に一致します。

aとの値が大きいbほど、反復ごとに実行されるステップ数が増加しますが、両方が定数である場合、複雑さは依然として線形になります。

于 2012-07-26T16:26:30.683 に答える
0

ステップサイズは問題ないと思います。遅い < 速い限り、リストにサイクルがある場合、2 つが一致します。

唯一の違いは、各反復で各ポインターが実行するステップ数が異なることです。

于 2012-07-26T18:58:34.503 に答える
0

よく私はいくつかの基本的な数学を使用して議論の方法でそれを理解しました. ループのあるリンクされたリストを想像してください。遅いポインターと速いポインターの両方が動き始めます。T をループの開始点、またはリスト自体が接続されているノードとします。スロー ポインターがこのノードに到達すると、ファスト ポインターはループ内に入ります。したがって、時針と分針を備えたこのループのような時計を想像してみてください.2つのポインターは、速度に関係なく、速度の公倍数で一致します.

于 2015-01-26T11:33:33.837 に答える