O(log n)は正確には何を意味するのか

time-complexity big-o


Big O Notationの実行時間と償却時間について学習しています。私はO(n)線形時間の概念を理解しています。つまり、入力のサイズがアルゴリズムの成長に比例して影響を与えることを意味します。たとえば、2次時間O(n 2などでも同じことが言えます。 、階乗によって成長するO(n!)回の置換ジェネレータなど。

たとえば、次の関数はO(n)です。これは、アルゴリズムが入力nに比例して大きくなるためです。

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

同様に、ネストされたループがある場合、時間はO(n 2)になります。

しかし、正確にはO(log n)とは何ですか?たとえば、完全な二分木の高さがO(log n)であるとはどういう意味ですか?

私は(たぶん詳細ではないかもしれませんが)対数が何であるかを知っています。つまり、log 10 100 = 2ですが、対数時間で関数を識別する方法を理解できません。




Answer 1 John Feminella


ログタイムで機能を特定する方法がわからない。

対数走時関数に共通する属性としては

  • 次の要素の選択は,いくつかの可能性のうちの1つであり
  • だけを選択する必要があります。

or

  • アクションが実行される要素はnの桁である。

これが、たとえば、電話帳で人を検索することがO(log n)である理由です。電話帳のすべての人を調べて適切な人を見つける必要はありません。代わりに、名前がアルファベット順になっている場所に基づいて調べるだけで、分割統治することができます。すべてのセクションで、最終的に誰かの電話番号を見つける前に、各セクションのサブセットを探索するだけで済みます。

もちろん、電話帳を大きくしても時間はかかりますが、追加サイズの比例増加のようにすぐには伸びません。


電話帳の例を拡張して、他の種類の操作とその実行時間を比較できます。電話帳には、一意の名前を持つビジネス(「イエローページ」)と一意の名前を持たない可能性のある人物(「ホワイトページ」)があると想定します。電話番号は多くても1人または1つのビジネスに割り当てられます。また、特定のページに切り替えるのに一定の時間がかかると仮定します。

ここでは、電話帳上で行うかもしれないいくつかの操作の実行時間を、最速から最長までご紹介します。

  • O(1)(最悪の場合):お店の名前が表示されているページとお店の名前を指定して、電話番号を見つけます。

  • O(1)(平均的なケース):人の名前が表示されているページとその名前を考慮して、電話番号を見つけます。

  • O(log n):人の名前を指定して、まだ検索していない本の部分の半分くらいのところからランダムなポイントを選び、その人の名前がそのポイントにあるかどうかを確認して、電話番号を見つけます。次に、本の人の名前のある部分のほぼ半分までこのプロセスを繰り返します。(これは人の名前のバイナリ検索です。)

  • O(n):電話番号に数字「5」が含まれるすべての人を検索します。

  • O(n):電話番号を指定して、その番号の人または企業を検索します。

  • O(n log n):プリンターのオフィスで取り違えがあり、電話帳にはすべてのページがランダムな順序で挿入されていました。各ページの名を確認し、そのページを新しい空の電話帳の適切な場所に配置して、正しいように順序を修正します。

以下の例では、印刷所に到着しました。電話帳が各住民や企業に郵送されるのを待っています。電話帳には郵送先を示すシールが貼ってあります。一人一冊の電話帳を、一人一冊の住人や企業に配布しています。

  • O(n log n):電話帳をパーソナライズしたいので、指定されたコピーで各個人または企業の名前を検索し、次に本の中でそれらの名前を丸で囲み、後援者に短いお礼状を書きます。 。

  • O(n 2):オフィスでミスが発生し、各電話帳のすべてのエントリに電話番号の末尾に「0」が追加されています。ホワイトアウトをいくつか取り、各ゼロを削除します。

  • O(n・n!):電話帳を出荷ドックにロードする準備ができました。残念ながら、本をロードすることになっていたロボットが問題を抱えています。本をランダムな順序でトラックに載せています!さらに悪いことに、すべての本をトラックに積み込んでから、それらが正しい順序になっているかどうかを確認し、そうでない場合は、積み下ろして最初からやり直します。 (これは恐ろしいbogoソートです。)

  • O(n n):ロボットが物を正しくロードするように修正します。翌日、同僚の1人がいたずらをして、荷受ロボットを自動印刷システムに接続します。ロボットが元の本を読み込もうとするたびに、ファクトリープリンターはすべての電話帳の複製を実行します。幸いなことに、ロボットのバグ検出システムは非常に高度で、ロボットがロードする複製本に遭遇したときにさらに多くのコピーを印刷しようとはしませんが、印刷されたすべてのオリジナルおよび複製の本をロードする必要があります。




Answer 2 fastcodejava


O(log N) は、基本的に時間は直線的に増加するのに対し、 n は指数関数的に増加することを意味します。したがって、 10 要素の計算に 1 秒かかる場合、 100 要素の計算には 2 秒、 1000 要素の計算には 3 秒というようになります。

それは O(log n) 、我々はアルゴリズム例えば、バイナリサーチの分割統治種類を行うとき。別の例は、配列を2つの部分に分割するたび、およびピボット要素を見つけるために O(N) 時間かかるたびのクイックソートです。したがって、 N O(log N)




Answer 3 Jørn Schou-Rode


この質問にはすでに多くの良い回答が投稿されていますが、私たちは本当に重要なものを見落としていると思います。

完全な二進木の高さがO(log n)であるとはどういうことでしょうか?

次の図は、バイナリツリーを示しています。各レベルに含まれるノードの数が、上のレベル(したがって、バイナリ)と比較して2倍になることに注目してください。

Binary tree

二分探索は、複雑度 O(log n) の例です。図1のツリーの最下位レベルのノードが、いくつかのソートされたコレクションのアイテムを表すとしましょう。バイナリ検索は分割統治アルゴリズムであり、この図は、この16項目のデータセットで検索するレコードを見つけるために(最大で)4つの比較がどのように必要になるかを示しています。

代わりに32個の要素を持つデータセットがあったとしましょう。上の図を続けてみると、データ量を増やしたときに木が1レベル深くなっただけなので、探しているものを見つけるためには5回の比較が必要になることがわかります。その結果、アルゴリズムの複雑さは対数的な順序で記述できます。

普通の紙に log(n) をプロットすると、 n が増加するにつれて曲線の上昇が減速するグラフになります。

O(log n)




Answer 4 2cupsOfTech


以下の説明では、完全にバランスのとれたバイナリツリーのケースを使用して、対数時間の複雑さを理解する方法を説明しています。

二進木は、サイズnの問題を、サイズ1の問題に到達するまで、サイズn/2のサブ問題に分割する場合です。

height of a binary tree

そして、それは、解決策に到達するために上記のツリーに必要な作業量であるO(log n)を取得する方法です。

O(log n)の時間的複雑さを持つ一般的なアルゴリズムは、再帰的関係がT(n/2)+O(1)であるバイナリ探索、すなわち、木の後続のレベルごとに問題を半分に分割し、一定量の追加作業を行うことです。




Answer 5 James Oravec


Overview

他の人は、ツリー図のような良い図例をあげています。私は簡単なコード例を見ませんでした。そこで、私の説明に加えて、異なるアルゴリズムのカテゴリの複雑さを説明するために、簡単な印刷文を持ついくつかのアルゴリズムを提供します。

最初に、Logarithmの一般的な概念が必要になります。これは、https://en.wikipedia.org/wiki/Logarithmから取得できます。自然科学は e と自然対数を使用します。コンピューターはバイナリベースであるため、工学の弟子はlog_10(ログベース10)を使用し、コンピューターの科学者はlog_2(ログベース2)を頻繁に使用します。自然対数の省略形が ln() として表示される場合があります。エンジニアは通常_10をオフにして、 log() を使用し、log_2は lg() と省略されます。すべてのタイプの対数は同じように増加します。そのため、これらは同じカテゴリの log(n) を共有します。

以下のコード例を見るときは、O(1)、O(n)、O(n^2)の順に見ることをお勧めします。それらを使いこなせたら、他のコードも見てみましょう。微妙な変更でも同じ分類になることを示すために、きれいな例とバリエーションを入れました。

O(1)、O(n)、O(logn)などを成長のクラスやカテゴリとして考えることができます。いくつかのカテゴリは、他のカテゴリよりも時間がかかります。これらのカテゴリは、アルゴリズムの性能を順序付ける方法を提供するのに役立ちます。いくつかは、入力nが成長するにつれて速く成長します。次の表は、成長が数値的に示されています。下の表では、log(n)をlog_2の上限と考えてください。

enter image description here

さまざまなビッグOカテゴリの簡単なコード例:

O(1)-一定時間の例:

  • アルゴリズム1:

アルゴリズム1はhelloを1回出力し、nに依存しないため、常に一定の時間で実行されるため、 O(1) です。

print "hello";
  • アルゴリズム2:

アルゴリズム2はhelloを3回出力しますが、入力サイズには依存しません。nが大きくなっても、このアルゴリズムはhelloを常に3回だけ出力します。言われている3は定数なので、このアルゴリズムも O(1) です。

print "hello";
print "hello";
print "hello";

O(log(n))-対数の例​​:

  • アルゴリズム3-これは「log_2」のように機能します

アルゴリズム3は、log_2(n)で実行されるアルゴリズムを示しています。forループのポスト操作がiの現在の値を2倍することに注意してください。つまり、 i は1から2、4、8、16、32に進みます。

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • アルゴリズム4-これは「log_3」のように機能します

アルゴリズム4はlog_3を示しています。注意してください i 27に1 3から9に行きます...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • アルゴリズム5-これは「log_1.02」のように機能します

アルゴリズム 5 は重要です。数が 1 よりも大きく、結果がそれ自身に対して繰り返し乗算される限り、対数アルゴリズムを見ていることを示すのに役立ちます。

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O(n)-線形時間の例:

  • アルゴリズム6

このアルゴリズムは、helloをn回印刷する単純なものです。

for(int i = 0; i < n; i++)
  print "hello";
  • アルゴリズム7

n/2=1/2*n.1/2定数を無視して、このアルゴリズムがO(n)であることがわかります。

for(int i = 0; i < n; i = i + 2)
  print "hello";

O(n * log(n))-nlog(n)の例:

  • アルゴリズム8

これを O(log(n))O(n) の組み合わせと考えてください。forループのネストは、 O(n*log(n)) の取得に役立ちます

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • アルゴリズム9

アルゴリズム9はアルゴリズム8に似ていますが、各ループでバリエーションが許可されているため、最終的な結果は O(n*log(n)) になります。

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O(n ^ 2)-nの2乗の例:

  • アルゴリズム10

O(n^2) は、標準のforループをネストすることで簡単に取得できます。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • アルゴリズム11

アルゴリズム10と似ていますが、いくつかのバリエーションがあります。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O(n ^ 3)-nの3乗の例:

  • アルゴリズム12

これはアルゴリズム10に似ていますが、2つのループの代わりに3つのループがあります。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • アルゴリズム13

アルゴリズム12と同様ですが、まだ O(n^3) 生成するいくつかのバリエーションがあります。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Summary

上記では、いくつかのわかりやすい例と、分析を実際に変更することなく、どのような微妙な変更を導入できるかを示すためのバリエーションを紹介しています。うまくいけば、あなたに十分な洞察を与えてくれるでしょう。