[解決済み] あるアルゴリズムの計算量がO(log log n)になる原因は何でしょうか？

質問

この前の質問 は、あるアルゴリズムがO(log n)の複雑性を持つ原因となり得る要因のいくつかを取り上げています。

あるアルゴリズムが時間計算量O(log log n)になる原因は何でしょうか？

どのように解決するのですか？

O(log log n)の項は様々な場所に現れますが、この実行時にたどり着くルートは通常2つあります。

平方根で縮小する

リンク先の質問への回答で述べたように、あるアルゴリズムが時間計算量O(log n)を持つ一般的な方法は、そのアルゴリズムが反復毎に入力のサイズをある定数倍で繰り返し削減することによって動作することです。 この場合、アルゴリズムはO(log n)回の繰り返しで終了しなければなりません。なぜなら、定数でO(log n)回除算した後、アルゴリズムは問題のサイズを0か1まで縮めなければならないからです。 これは、例えば、バイナリサーチの複雑さがO(log n)である理由です。

興味深いことに、O(log log n)という形の実行時間を得るために、問題のサイズを縮小する同様の方法がある。 各層で入力を半分に分割する代わりに、次のようにするとどうなるか？ サイズの平方根を取る 各レイヤーで

たとえば、65,536という数字を例に挙げてみましょう。 これを2で何回割ったら1になるでしょうか？ そうすると、次のようになります。

• 65,536 / 2 = 32,768
• 32,768 / 2 = 16,384
• 16,384 / 2 = 8,192
• 8,192 / 2 = 4,096
• 4,096 / 2 = 2,048
• 2,048 / 2 = 1,024
• 1,024 / 2 = 512
• 512 / 2 = 256
• 256 / 2 = 128
• 128 / 2 = 64
• 64 / 2 = 32
• 32 / 2 = 16
• 16 / 2 = 8
• 8 / 2 = 4
• 4 / 2 = 2
• 2 / 2 = 1

この処理は16ステップで、65,536＝2の場合にも ¹⁶ .

しかし、各レベルで平方根をとると、次のようになります。

• √65,536 = 256
• √256 = 16
• √16 = 4
• √4 = 2

2になるまでに4ステップしか必要ないことに注目してください。

まず、直感的な説明です。nと√nは何桁の数字でしょうか？数nの桁数は約対数nであり、約対数(√n)=log (n ^1/2 ) = (1/2) log n 桁で√nになります。つまり、平方根をとるたびに、数の桁数がおよそ半分になるのです。ある定数(例えば2)になるまでには、k個の量をO(log k)回しか半分にできないので、これは、ある定数(例えば2)になるまでには、O(log log n)回しか平方根を取ることができないことを意味している。

さて、これを厳密にするための計算をしてみましょう。上の数列を2の累乗で書き換えてみましょう。

• √65,536 = √2 ¹⁶ = (2 ¹⁶ ) ^1/2 = 2 ⁸ = 256
• √256 = √2 ⁸ = (2 ⁸ ) ^1/2 = 2 ⁴ = 16
• √16 = √2 ⁴ = (2 ⁴ ) ^1/2 = 2 ² = 4
• √4 = √2 ² = (2 ² ) ^1/2 = 2 ¹ = 2

2という順序を踏んでいることに注目してください。 ¹⁶ → 2 ⁸ → 2 ⁴ → 2 ² → 2 ¹ . 反復のたびに、2のべき乗の指数を半分にする。 これは興味深いことで、私たちがすでに知っていること、つまり、数kを半分に割って0になるまでにO(log k)回しかできないことにつながるからです。

そこで、任意の数nをとって、n = 2と書くと ^k . nの平方根を取るたびに、この式の指数が半分になる。 したがって、kが1以下になる前に適用できる平方根はO(log k)だけです（その場合、nは2以下になります）。 n = 2なので ^k ということは、k = log <サブ 2 nであるから、取られる平方根の数はO(log k) = O(log log n)となる。 したがって、問題を元の問題サイズの平方根であるサイズの部分問題に繰り返し縮小することで機能するアルゴリズムがあれば、そのアルゴリズムはO(log log n)ステップ後に終了します。

実際の例としては バンエムデボアス木 (vEB-tree）データ構造です。 vEB-treeは、範囲0 ... の整数を格納するための特殊なデータ構造である。木のルートノードには√N個のポインタがあり，0 ... N - 1の範囲を分割する．N - 1の範囲を√N個のバケットに分割し，それぞれがおよそ√N個の整数の範囲を保持する． これらのバケットは内部でそれぞれ√(√ N)個のバケットに分割され，各バケットはおよそ√(√ N)個の要素を保持する． 木構造をたどるには、根から始めて、どのバケットに属するかを決定し、適切な部分木を再帰的にたどっていくことになる。 vEB-treeの構造上、どのサブツリーに降りるかはO(1)時間で決定できるので、O(log log N)ステップでツリーの底に到達することになる。 従って、vEB-treeのルックアップにはO(log log N)の時間しかかからない。

もう一つの例は ホップクロフト-フォーチュン最接近点アルゴリズム . このアルゴリズムは、2次元の点の集まりの中から最も近い2点を見つけようとするものである。 これは、バケツのグリッドを作成し、それらのバケツに点を分散させることで動作します。 アルゴリズムのどの時点でも、√N 個以上の点を含むバケツが見つかった場合、アルゴリズムはそのバケツを再帰的に処理します。 したがって、再帰の最大深さはO(log log n)であり、再帰木の分析を用いて、木の各層がO(n)の仕事をすることを示すことができる。 したがって、このアルゴリズムの総実行時間はO(n log log n)である。

小さな入力に対するO(log n)アルゴリズム

他にも、サイズO(log n)のオブジェクトに対して二項探索のようなアルゴリズムを用いることで、実行時間O(log log n)を実現するものがある。例えば x-ファストトライ データ構造は、高さO(log U)の木の層に対して二項探索を行うので、そのいくつかの操作の実行時間はO(log log U)である。また、関連する y-ファストトライ O(log U)ノードのBSTをバランスよく維持することで、O(log log U)の実行時間を実現しています。また タンゴツリー および関連する マルチディスプレイ・ツリー データ構造は、それぞれO(log n)個の項目を含むツリーを維持するため、解析ではO(log log n)項となる。

その他の例

他のアルゴリズムでは、他の方法で実行時間O(log log n)を達成しています。 補間探索 は、ソートされた配列から数を見つけるために、実行時間O(log log n)を期待されていますが、解析はかなり複雑です。 最終的には、反復計算の回数が、n ^{2 -k} ≦2であり、log log nが正しい解となる。のようなアルゴリズムもある。 チェリトン-タルヤンMSTアルゴリズム 複雑な制約付き最適化問題を解くことで、O(log log n)を含む実行時間を実現している。

お役に立てれば幸いです。