CLRS アルゴリズム ブックの問題 31.1-12 は、次の質問をします。
与えられた
βビット (2 進数) 整数を 10 進数表現に変換する効率的なアルゴリズムを与えてください。長さが最大で の整数の乗算または除算にβ時間がかかるM(β)場合、2 進数から 10 進数への変換は 時間内に実行できると主張しΘ( M(β) lg β)ます。(ヒント:分割統治法を使用して、結果の上半分と下半分を別々の再帰で取得します。
時間を尋ねΘ( M(β) lg β)ます。lg β再帰ツリーの高さだけを考えると、分割統治アルゴリズムでそれがどのように可能になるのでしょうか? 意図したソリューションが何であるかを誰かが知っていますか?
ヒントが機能するには、M(β) が線形関数である必要があります。特に、M(β) ≈ 2·M(β/2) です。
それが与えられた場合、明らかな解決策があります。データを部分に再帰的に分割し、部分を個別に処理し、結果を結合します。再帰のレベル k では、2ᵏ 個の部分があり、それぞれの長さはおよそ β/(2ᵏ) ビット、つまり合計およそ β です。レベル k での処理には 2ᵏ·M(β/(2ᵏ)) ≈ M(β) のコストがかかり、合計時間は O(M(β)·lg β) になります。
値 u を β ビットで分割し、その 2 つの部分 (v,w) を処理するには、2·d または 2·d+1 = ⌊β·ln(2)/ln(10)⌋ とします。v = ⌊u/10ᵈ⌋ と w = uv·10ᵈ とする。