私はSteinのAlgorithm（binary GCD algorithm）の再帰関係を考えようとしていますが、それを追跡する能力はまったく新しいものではありません。
私は、値そのものではなく値を表すために総ビット数を扱うという事実だけでなく、複数のパスと再帰呼び出しに完全に困惑しています。
これがアルゴリズムです。
stein(u, v):
if either of u or v are 0: return their sum.
if either of u or v are 1: return 1.
if both u and v are even: return 2 * stein(u/2, v/2)
if u is even and v is odd: return stein(u/2, v)
if u is odd and v is even: return stein(u, v/2)
if both u and v are odd: return stein(larger-smaller/2, smaller)
再帰関係T（n）を見つけようとしているここで、nは、uとvの両方を表すのに必要な総ビット数です。ここでの最初のステップは、ワーストケースのパフォーマンスが発生したときにうまくいくはずだと思います。
除算のたびにビット数が1ずつ減ると思いますが、これまでのところ私が理解していることのほとんどについてです。
私はアルゴリズムをトレースしようとしましたが、役に立ちませんでした。 私は「Knuth Vol。2の関連部分も読んだことがありますが、それは私にはほとんど意味をなさないので、現在の私の理解の範囲外です」と思います。
回答：
回答№1の場合は3あなたはstein（u、v）の値ではなく、uとvのビット数を表す再帰関係が欲しいので、それを少し考えてみましょう。
任意のuとvを考えると、最善と最悪の場合は何ですか？
ベストケース（私たちはすぐに終了します）：一定期間のケースの1つです。
最悪の場合：stein（u / 2、v / 2）、stein（u、v / 2）、またはstein（より大きい/小さい/ 2、小さい）への再帰呼び出し
最初のシナリオでは、値を2分の1にすることで、2つの2進数を単純に削除します。そのためには、1つの操作でコストがかかります。
2番目のシナリオでは、1つの値を除算するだけなので、最初の値よりも1桁だけ少なくなります。これには1つの演算が必要でした。T（n）= T（n-1）+ 1
3番目のシナリオは、より複雑になります。 減算は、nのすべての数字を反復します。これは、m桁を失うがnステップ（減算）を使用した場合、繰り返しはT（n）> = T（n-m）+ nになることを意味します。まだmを見つける必要があり、このステップで多くの桁が除去されることを証明できれば（例：m = n / 2）、繰り返しが遅すぎることはないかもしれません。
残念ながら、非常に悪いシナリオを簡単に思いつくことができます。
vを3に設定します。 これはそれが奇数であることを保証し、それは常に2つのうちの小さい方になるでしょう。（uv）/ 2が奇数であり続けるようにuを設定するなら、再発はその3番目のケースに行き続けるでしょう3、（uv）/ 2はuより1桁だけ短くなります。これは、最悪の場合、mが1であることを意味します。==> T（n）= T（n-1）+ n
その悪いシナリオの例： （21,3） - >（9,3） - >（3,3）v "= v * 2 + 3を取ることで、より大きな数を構成することができます。ご覧のように、これらの"悪い "数の増加は一度に1つの2進数と私たちは常に3番目の道を進むように私たちを導くでしょう。だからこそmは1です。
その最後の再発シナリオは残念ながらO（n * n）です。
回答№2の場合は0
あなたはに依存するルールを探しています（問題のサイズに対して）できるだけ大きな部分問題のサイズで関数を再帰的に評価します。 1つ少ないビットで副問題を解くことを必要とする2つの規則があります。 u または v 変です。 奇数は変化せず、偶数は可能な限り長い間偶数のままであるべきです。これは、次のことが最悪の場合であることを示唆しています。 u = 3 そして v=2^n いくつかのための n。の実行時間 stein この場合、入力ビット数は線形です。