Amarengo

Articles and news

アルゴリズムがO(log log n)複雑さを持つ原因は何ですか?

O(log log n)用語はさまざまな場所に表示されますが、通常、このランタイムに到着する2つの主要なルートがあります。

平方根で縮小する

リンクされた質問への回答で述べたように、アルゴリズムが時間の複雑さO(log n)を持つ一般的な方法は、そのアルゴリズムが各反復で一定の係数だけ入力のサイズを繰り返しカットすることによって動作することです。 この場合、o(log n)を定数で除算した後、アルゴリズムは問題のサイズを0または1に縮小する必要があるため、アルゴリズムはO(log n)反復後に終了 これが、たとえば、バイナリ検索の複雑さO(log n)がある理由です。

興味深いことに、o(log log n)という形式のランタイムを生成する問題のサイズを縮小する同様の方法があります。 各レイヤーで入力を半分に分割する代わりに、各レイヤーでサイズの平方根を取るとどうなりますか?

たとえば、65,536という数を取りましょう。 私たちが1になるまで、これを2で割る必要がありますか? これを行うと、次のようになります

  • 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=216の場合もあります。

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

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

それだけで2にすべての方法を取得するために四つのステップを取ることに注意してくださ これはなぜですか?

まず、直感的な説明。 数字nと√nには何桁の数字がありますか? 数nには約log n桁があり、√nには約log(√n)=log(n1/2)=(1/2)log n桁があります。 これは、平方根を取るたびに、数字の桁数を約半分にしていることを意味します。 定数(たとえば、2)に下がる前に数量k O(log k)を半分にすることしかできないので、これは、数を定数(たとえば、2)に減らす前に平方根O(log log n)回しか取るこ

さて、これを厳密にするためにいくつかの数学をしましょう。 Le’tsは、上記のシーケンスを二つのべき乗の観点から書き直します:

  • √65,536 = √216 = (216)1/2 = 28 = 256
  • √256 = √28 = (28)1/2 = 24 = 16
  • √16 = √24 = (24)1/2 = 22 = 4
  • √4 = √22 = (22)1/2 = 21 = 2

私たちはシーケンスに従ったことに注意してくださ216 → 28 → 24 → 22 → 21. 各反復で、2のべき乗の指数を半分にカットします。 これは私たちがすでに知っていることにつながっているので、興味深いことです-ゼロになる前に、数kを半分のO(log k)回にしか分割できません。

だから、任意の数nを取り、それをn=2kと書く。 Nの平方根を取るたびに、この方程式の指数を半分にします。 したがって、kが1以下に低下する前に適用されるO(log k)平方根のみが存在する可能性があります(この場合、nは2以下に低下します)。 N=2kなので、これはk=log2nであることを意味し、したがって取られる平方根の数はO(log k)=O(log log n)です。 したがって、問題を元の問題サイズの平方根であるサイズの部分問題に繰り返し縮小することで機能するアルゴリズムがある場合、そのアルゴリズ

実際の例として、van Emde Boas tree(vEB-tree)データ構造があります。 VEBツリーは、0の範囲の整数を格納するための特殊なデータ構造です。.. N-1 それは次のように動作します:ツリーのルートノードには√Nポインタがあり、範囲0を分割します。.. N-1をroughly Nバケットに入れ、それぞれが約N N整数の範囲を保持します。 これらのバケットは、それぞれが内部的にroughly(√N)バケットに細分され、それぞれがおおよそ√(√N)要素を保持します。 ツリーをトラバースするには、ルートから開始し、所属するバケットを決定してから、適切なサブツリー内で再帰的に続行します。 VEBツリーが構造化されているため、どのサブツリーに降下するかをO(1)時間で決定できるため、O(log log N)ステップの後にツリーの底に到達します。 したがって、vEBツリー内の検索にはO(log log N)のみ時間がかかります。

もう一つの例は、Hopcroft-Fortune closest pair of pointsアルゴリズムです。 このアルゴリズムは、2Dポイントのコレクション内で最も近い2つのポイントを見つけようとします。 これは、バケットのグリッドを作成し、それらのバケットにポイントを配布することによ アルゴリズムの任意の時点で、√N以上のポイントを持つバケットが見つかった場合、アルゴリズムはそのバケットを再帰的に処理します。 したがって、再帰の最大深度はO(log log n)であり、再帰ツリーの分析を使用すると、ツリー内の各レイヤーがO(n)機能することが示されます。 したがって、アルゴリズムの合計実行時間はO(n log log n)です。

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

サイズO(log n)のオブジェクトに対するバイナリ検索のようなアルゴリズムを使用してO(log log n)ランタイムを達成する他のアルゴリズムがいくつかあります。 たとえば、x-fast trieデータ構造は、高さO(log U)のツリーでのレイヤーに対するバイナリ検索を実行するため、その操作の一部のランタイムはO(log log U)になります。 関連するy-fast trieは、O(log u)ノードのバランスの取れたBstをそれぞれ維持することによって、O(log log U)ランタイムの一部を取得し、それらのツリーでの検索を時間O(log log U)で実行できるようにします。 Tangoツリーと関連するマルチプレイツリーのデータ構造は、それぞれO(log n)項目を含むツリーを維持するため、分析でO(log log n)項になります。

他の例

他のアルゴリズムは、他の方法でランタイムO(log log n)を達成します。 補間検索では、ソートされた配列内の数値を見つけるために実行時O(log log n)が期待されていますが、分析はかなり関与しています。 最終的に、この分析は、反復回数がn2-k≥2となるような数kに等しいことを示すことによって機能し、log log nが正しい解であることを示します。 Cheriton-Tarjan mstアルゴリズムのようないくつかのアルゴリズムは、複雑な制約付き最適化問題を解くことによってO(log log n)を含む実行時に到着します。

これが助けになることを願っています!

コメントを残す

メールアドレスが公開されることはありません。