Big O Notation の実行時間と償却時間について学習しています。O(n)線形時間の概念を理解しています。つまり、入力のサイズがアルゴリズムの成長に比例して影響することを意味します...たとえば、二次時間O(n 2 )などについても同じことが言えます.アルゴリズムでさえ階乗によって成長するO(n!)回の順列ジェネレーターなど。
たとえば、アルゴリズムは入力nに比例して大きくなるため、次の関数はO(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という意味で、対数が何であるかは知っていますが（詳細ではないかもしれませんが）、対数時間で関数を特定する方法がわかりません。
ログ時間で関数を特定する方法がわかりません。
対数実行時関数の最も一般的な属性は次のとおりです。
また
たとえば、電話帳で人を検索すると O(log n) になるのはこのためです。適切な人を見つけるために、電話帳のすべての人をチェックする必要はありません。代わりに、名前がアルファベット順にどこにあるかに基づいて探すことで、単純に分割統治することができ、最終的に誰かの電話番号を見つける前に、各セクションのサブセットを探索するだけで済みます.
もちろん、電話帳が大きいほど時間がかかりますが、追加サイズの比例増加ほど速くは拡大しません。
電話帳の例を拡張して、他の種類の操作とその実行時間を比較できます。電話帳には、一意の名前を持つビジネス(「イエロー ページ」) と、一意の名前を持たない人(「ホワイト ページ」) があると仮定します。電話番号は、多くても 1 人の個人または企業に割り当てられます。また、特定のページをめくるのに一定の時間がかかると仮定します。
電話帳で実行する可能性のあるいくつかの操作の実行時間は、最速のものから最も遅いものまで次のとおりです。
O(1) (最悪の場合):ビジネスの名前が掲載されているページとビジネス名から、電話番号を見つけます。
O(1) (平均的な場合):人物の名前が掲載されているページとその名前から、電話番号を見つけます。
O(log n):人の名前が与えられたら、まだ検索していない本の部分の約半分を無作為に選んで電話番号を見つけ、次にその人の名前がその場所にあるかどうかを確認します。次に、その人物の名前が書かれている本の途中まで、このプロセスを繰り返します。(これは人の名前の二分探索です。)
O(n):電話番号に数字「5」が含まれるすべての人を検索します。
O(n):電話番号を指定して、その番号を持つ個人または企業を見つけます。
O(n log n):印刷所で取り違えがあり、電話帳のすべてのページがランダムな順序で挿入されていました。各ページの最初の名前を確認し、そのページを新しい空の電話帳の適切な場所に配置して、正しい順序になるように修正します。
以下の例では、現在印刷所にいます。電話帳は、各居住者または企業に郵送されるのを待っています。各電話帳には、郵送先を示すステッカーが貼られています。すべての個人または企業は、1 つの電話帳を取得します。
O(n log n):電話帳をパーソナライズしたいので、指定されたコピーで各個人または企業の名前を見つけ、その名前を本に丸で囲み、ご愛顧に対する短い感謝状を書きます。 .
O(n 2 ):オフィスでミスが発生し、各電話帳のすべてのエントリで、電話番号の末尾に余分な「0」が追加されました。ホワイトアウトを取り、各ゼロを削除します。
O(n · n!):電話帳を配送ドックに積み込む準備が整いました。残念なことに、本を積み込むはずだったロボットが大混乱に陥りました。無作為な順序で本をトラックに積み込んでしまったのです。さらに悪いことに、すべての本をトラックに積み込み、順番が正しいかどうかをチェックし、そうでない場合は、積み下ろして最初からやり直します。（これは恐ろしいボゴソートです。）
O(n n ):ロボットが正しく読み込まれるように修正します。翌日、同僚の 1 人があなたにいたずらをし、搬入ドックのロボットを自動印刷システムに配線します。ロボットがオリジナルの本をロードするたびに、工場のプリンターがすべての電話帳を複製します。幸いなことに、ロボットのバグ検出システムは十分に洗練されているため、ロボットは読み込み用の複製本に遭遇したときにそれ以上の部数を印刷しようとはしませんが、印刷された元の本と複製本はすべて読み込む必要があります。
O(log N)n基本的に、時間が指数関数的に増加する一方で、時間が直線的に増加することを意味します。したがって、要素の計算に数秒かかる場合1は、10要素の計算に数秒、要素の計算に数秒、というようになります。210031000
それはO(log n)、二分探索などの分割統治型のアルゴリズムを実行するときです。もう 1 つの例は、配列を 2 つの部分に分割するたびにO(N)ピボット要素を見つけるのに時間がかかるクイック ソートです。したがって、 N O(log N)
この質問にはすでに多くの良い回答が投稿されていますが、重要な回答、つまり図解された回答が本当に欠けていると思います。
完全な二分木の高さが O(log n) であるとはどういう意味ですか?
次の図は、バイナリ ツリーを示しています。各レベルには、上のレベルに比べて 2 倍の数のノードが含まれていることに注意してください (したがって、binary )。
二分探索は複雑な例O(log n)です。図 1 のツリーの最下位レベルにあるノードが、ソートされたコレクション内の項目を表しているとしましょう。二分探索は分割統治アルゴリズムであり、図は、この 16 項目のデータセットで検索対象のレコードを見つけるために (最大で) 4 回の比較が必要であることを示しています。
代わりに、32 個の要素を持つデータセットがあるとします。上の図を続けて、検索対象を見つけるために 5 つの比較が必要であることを確認します。これは、データの量を掛けたときにツリーが 1 レベル深く成長しただけだからです。その結果、アルゴリズムの複雑さは対数次数として記述できます。
log(n)普通の紙にプロットすると、曲線の上昇がn増加するにつれて減速するグラフが得られます。
概要
他の人は、ツリー図などの良い図の例を示しています。簡単なコード例は見当たりませんでした。そのため、私の説明に加えて、アルゴリズムのさまざまなカテゴリの複雑さを説明するために、簡単な print ステートメントをいくつかのアルゴリズムに提供します。
まず、 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 の上限と考えてください。
さまざまな Big O カテゴリの簡単なコード例:
O(1) - 一定時間の例:
アルゴリズム 1 は hello を 1 回出力し、n に依存しないため、常に一定の時間で実行されるため、O(1).
print "hello";
アルゴリズム 2 は hello を 3 回出力しますが、入力サイズには依存しません。n が大きくなっても、このアルゴリズムは常に hello を 3 回しか出力しません。そうは言っても 3 は定数なので、このアルゴリズムもO(1)です。
print "hello";
print "hello";
print "hello";
O(log(n)) - 対数の例:
アルゴリズム 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 を示しています。通知iは 1 から 3 から 9 から 27 まで続きます...
for(int i = 1; i <= n; i = i * 3)
print "hello";
アルゴリズム 5 は重要です。数値が 1 よりも大きく、結果がそれ自体に対して繰り返し乗算される限り、対数アルゴリズムを見ていることを示すのに役立つからです。
for(double i = 1; i < n; i = i * 1.02)
print "hello";
O(n) - 線形時間の例:
このアルゴリズムは単純で、hello を n 回表示します。
for(int i = 0; i < n; i++)
print "hello";
このアルゴリズムは、hello を n/2 回出力するバリエーションを示しています。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) 例:
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 はアルゴリズム 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 の二乗 例:
O(n^2)は、標準の for ループをネストすることで簡単に取得できます。
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
print "hello";
アルゴリズム 10 に似ていますが、いくつかのバリエーションがあります。
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j = j + 2)
print "hello";
O(n^3) - n 立方 例:
これはアルゴリズム 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";
アルゴリズム 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";
概要
上記は、いくつかの単純な例と、実際には分析を変更しない微妙な変更を導入できることを示すのに役立つバリエーションを示しています。うまくいけば、それはあなたに十分な洞察を与えるでしょう.
以下の説明では、完全にバランスの取れた二分木の場合を使用して、対数時間の複雑さを得る方法を理解できるようにしています。
二分木は、サイズ n の問題が、サイズ 1 の問題に到達するまで、サイズ n/2 のサブ問題に分割される場合です。
そして、それが、ソリューションに到達するために上記のツリーで実行する必要がある作業の量である O(log n) を取得する方法です。
O(log n) 時間の複雑さを持つ一般的なアルゴリズムは、再帰関係が T(n/2) + O(1) である二分探索です。つまり、ツリーの後続のレベルごとに、問題を半分に分割し、一定量の追加作業を行います。
次の関数があるとします。
1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2^n elements.
次に、log 2 (n) 時間かかります。大まかに言えば、ビッグ O 表記法は、関係が大きな n に対してのみ真である必要があり、定数因子と小さな項は無視できることを意味します。
対数
では、対数が実際に何であるかを完全に理解してみましょう。
ロープがあり、それを馬に結び付けたと想像してください。ロープが馬に直接結び付けられている場合、馬が引き離すのに必要な力 (たとえば、男性から) は、直接 1 です。
ロープがポールの周りに輪になっていると想像してください。逃げる馬は何倍も強く引っ張らなければなりません。回数はロープの粗さやポールの大きさにもよりますが、10倍の力（ロープが1回転するとき）を想定してみましょう。
ロープが 1 回ループすると、馬は 10 倍の力で引っ張る必要があります。人間が馬にとって非常に難しいと判断した場合は、ロープを再びポールに巻き付けて、ロープの強度をさらに 10 倍にすることができます。3 回目のループでは、強度がさらに 10 倍になります。
ループごとに、値が 10 ずつ増加することがわかります。数値を取得するために必要なターン数は、数値の対数と呼ばれます。つまり、強度を 1000 倍にするには 3 つのポストが必要であり、強度を 1000 倍にするには 6 つのポストが必要です。 1,000,000。
3 は 1,000 の対数、6 は 1,000,000 (底 10) の対数です。
では、O(log n) とは実際には何を意味するのでしょうか?
上記の例では、「成長率」はO(log n)です。追加のループごとに、ロープが処理できる力は 10 倍になります。
Turns | Max Force
0 | 1
1 | 10
2 | 100
3 | 1000
4 | 10000
n | 10^n
上記の例では基数 10 を使用していましたが、幸いなことに、大きな o 表記について話すとき、対数の基数は重要ではありません。
ここで、1 から 100 までの数字を推測しようとしているとします。
Your Friend: Guess my number between 1-100!
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!
これを正しく理解するには、7 回の推測が必要でした。しかし、ここでの関係は何ですか？追加の各推測から推測できる項目の最大数は?
Guesses | Items
1 | 2
2 | 4
3 | 8
4 | 16
5 | 32
6 | 64
7 | 128
10 | 1024
グラフを使用すると、二分探索を使用して 1 ～ 100 の数字を推測する場合、最大7 回の試行で済むことがわかります。128 個の数字がある場合、7 回の試行で数字を推測することもできますが、129 個の数字の場合、最大で8 回の試行が必要になります (対数に関して、ここでは、128 の値の範囲に対して 7 回の推測が必要であり、1024 の値の範囲に対して 10 回の推測が必要です)。 . 7 は 128 の対数、10 は 1024 の対数 (底 2))。
「せいぜい」を太字にしたことに注意してください。Big-O 表記は、常に最悪のケースを指します。運が良ければ、1 回の試行で数を推測できるため、最良のケースは O(1) ですが、それは別の話です。
推測ごとに、データセットが縮小していることがわかります。アルゴリズムが対数時間を持っているかどうかを識別する良い経験則は、反復ごとにデータセットが特定の順序で縮小するかどうかを確認することです
O(n log n) はどうですか?
最終的に、線形時間O(n log(n))アルゴリズムに出くわします。上記の経験則が再び適用されますが、今回は対数関数を n 回実行する必要があります。たとえば、リストのサイズを n 回縮小します。これはマージソートなどのアルゴリズムで発生します。
アルゴリズムの時間が n log n であるかどうかは簡単に識別できます。リスト (O(n)) を反復する外側のループを探します。次に、内部ループがあるかどうかを確認します。内側のループが反復ごとにデータセットをカット/削減している場合、そのループは (O(log n)) であり、全体的なアルゴリズムは = O(n log n)です。
免責事項: ロープ対数の例は、W.Sawyer による優れた Mathematician's Delight の本から引用しました。
対数実行時間 ( ) は基本的に、入力サイズの対数O(log n)に比例して実行時間が増加することを意味します。例として、10 個のアイテムに最大である程度の時間がかかり、100 個のアイテムに最大で10,000 個のアイテムがかかる場合、は最大で時間の複雑さのように見えます。x2x4xO(log n)
O(log N) は、時間は N の桁数に比例すると直感的に考えることができます。
操作が入力の各桁またはビットに対して一定時間の作業を実行する場合、操作全体には、入力の大きさではなく、入力の桁数またはビット数に比例する時間がかかります。したがって、O(N) ではなく O(log N) です。
操作が一連の一定時間の決定を行い、それぞれが考慮される入力のサイズを半分にする (3、4、5 の係数で縮小する) 場合、全体では対数底 2 (底 3) に比例する時間がかかります。 、基数 4、基数 5...) O(N) ではなく、入力のサイズ N です。
等々。
log b (n) とは?
これは、サイズ 1 のセクションに到達する前に、長さ n の丸太を繰り返し b 等分に切断できる回数です。
O(log n) で実行されるアルゴリズムを頭の中で視覚化するために常に必要だった最良の方法は次のとおりです。
問題のサイズを倍数で大きくした場合 (つまり、そのサイズを 10 倍した場合)、作業は追加の量だけ増加します。
これをバイナリ ツリーの質問に適用すると、適切なアプリケーションが得られます。バイナリ ツリーのノード数を 2 倍にしても、高さは 1 (加算量) だけ増加します。もう一度 2 倍にしても、1 だけ増加します (明らかに、バランスが保たれていると想定しています)。そうすれば、問題のサイズが倍増したときに作業量が 2 倍になるのではなく、作業量がわずかに増えるだけです。これが、O(log n) アルゴリズムが優れている理由です。
分割統治アルゴリズムには、通常logn、実行時間の要素があります。これは、入力の半分化が繰り返されることに起因します。
二分探索の場合、反復ごとに入力の半分を破棄します。Big-O 表記では、log は対数底 2 であることに注意してください。
編集: 前述のように、対数の基数は問題ではありませんが、アルゴリズムの Big-O パフォーマンスを導出する場合、対数係数は半分になるため、基数 2 と考えます。
O(log n) は少し誤解を招きます。より正確には、O(log 2 n)、つまり (底が 2 の対数) です。
すべてのノードには 2つの子ノード(log 2 nの「2」に注意) があるため、平衡二分木の高さは O(log 2 n) です。したがって、n 個のノードを持つツリーの高さは log 2 n になります。
もう 1 つの例は二分探索です。実行時間は O(log 2 n) です。これは、ステップごとに探索空間を 2 で割るためです。
簡単に言えば、アルゴリズムの各ステップで、作業を半分に減らすことができます。（漸近的に3番目、4番目、...と同等）
これは単に、このタスクに必要な時間が log(n) で増加することを意味します (例: n = 10 の場合は 2 秒、n = 100 の場合は 4 秒、...)。精度の詳細については、 Binary Search AlgorithmとBig O Notationに関するウィキペディアの記事を参照してください。
O(log n)対数に比例する時間量で機能する関数 (またはアルゴリズム、またはアルゴリズムのステップ) を指します (通常、ほとんどの場合、基数 2 ですが、常にではありません。いずれにせよ、big-O 表記法では重要ではありません*)。入力のサイズ。
対数関数は指数関数の逆です。別の言い方をすれば、入力が指数関数的に増加する場合 (通常は直線的に考えるのではなく)、関数は直線的に増加します。
O(log n)実行時間は、（理想的には）毎回作業を半分に削減しているため、あらゆる種類の分割統治アプリケーションで非常に一般的です。分割または征服のステップのそれぞれで、一定時間の作業 (または、一定時間ではないが時間の増加が よりも遅い作業) を行っている場合、O(log n)関数全体はO(log n)です。代わりに、各ステップが入力に対して線形時間を必要とすることはかなり一般的です。これは合計で の時間計算量になりO(n log n)ます。
二分探索の実行時間の複雑さはその一例ですO(log n)。これは、バイナリ検索では、配列を半分に分割し、各ステップで半分だけに焦点を当てることにより、後の各ステップで入力の半分を常に無視しているためです。各ステップは一定時間です。二分探索では、考慮している配列の大きさに関係なく、次に何をすべきかを理解するために 1 つの要素をキーと比較するだけでよいからです。したがって、おおよそ log(n)/log(2) ステップを実行します。
マージソートの実行時間の複雑さは、その一例ですO(n log n)。これは、各ステップで配列を半分に分割しているため、合計で約 log(n)/log(2) ステップになるためです。ただし、各ステップでは、すべての要素に対してマージ操作を実行する必要があります (n/2 要素の 2 つのサブリストに対する 1 つのマージ操作であるか、n/4 要素の 4 つのサブリストに対する 2 つのマージ操作であるかは関係ありません。各ステップで n 要素に対してこれを行います)。したがって、全体の複雑さはO(n log n)です。
* Big-O 記法は、定義上、定数は重要ではないことに注意してください。また、対数の底のルールの変更により、異なる底の対数間の唯一の違いは定数係数です。
対数関数をグラフィカルな電卓などでプロットすると、線形関数よりもさらにゆっくりと上昇することがわかります。
これが、対数時間の複雑さを持つアルゴリズムが非常に求められている理由です。非常に大きな n (たとえば、n = 10^8 としましょう) の場合でも、許容できる以上のパフォーマンスを発揮します。
実際、n 要素のリストがあり、そのリストからバイナリ ツリーを作成する場合 (分割統治アルゴリズムのように)、サイズ 1 のリスト (葉) に達するまで 2 で分割し続けます。
最初のステップで、2 で割ります。次に、2 つのリスト (2^1) があり、それぞれを 2 で割ると、4 つのリスト (2^2) になり、もう一度割ると、8 つのリスト (2^3) になります。 )など、リストのサイズが 1 になるまで
それはあなたに式を与えます：
n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps
(各辺の lg を取得します。lg は底が 2 の対数です)
昔、Kormen などの本で読んだ興味深いものを追加できます。さて、問題空間で解決策を見つけなければならない問題を想像してみてください。この問題空間は有限でなければなりません。
ここで、アルゴリズムのすべての反復で、このスペースの一部を切り捨てることを証明できれば、それは制限以上です。これは、アルゴリズムが O(logN) 時間で実行されていることを意味します。
ここでは、絶対的な制限ではなく、相対的な制限について話していることを指摘しておく必要があります。二分探索は古典的な例です。各ステップで、問題スペースの 1/2 を破棄します。しかし、そのような例は二分探索だけではありません。何らかの方法で、各ステップで問題空間の少なくとも 1/128 を捨てることを証明したとします。つまり、プログラムはまだ O(logN) 時間で実行されていますが、二分探索よりも大幅に遅くなります。これは、再帰アルゴリズムを分析する上で非常に良いヒントです。多くの場合、各ステップで再帰が複数のバリアントを使用しないことを証明できます。これにより、問題空間の一部が切り捨てられます。
for ループの例を挙げることができます。概念を理解すると、さまざまなコンテキストで理解しやすくなるかもしれません。
これは、ループ内でステップが指数関数的に増加することを意味します。例えば
for (i=1; i<=n; i=i*2) {;}
このプログラムの O 表記の複雑さは O(log(n)) です。手でループしてみましょう (n は 512 から 1023 の間 (1024 を除く) です):
step: 1 2 3 4 5 6 7 8 9 10
i: 1 2 4 8 16 32 64 128 256 512
n は 512 から 1023 の間ですが、反復は 10 回しか行われません。これは、ループ内のステップが指数関数的に増加し、10 回の繰り返しで終了に到達するためです。
x の (底が a の) 対数は、a^x の逆関数です。
対数は指数の逆数だと言っているようなものです。
指数関数が非常に速く成長する場合、対数は（逆に）非常に遅く成長します。
O(n) と O(log(n)) の違いは非常に大きく、O(n) と O(a^n) (a は定数) の違いと同様です。
検索は次のようになるため、完全なバイナリの例は O(ln n) です。
1 2 3 4 5 6 7 8 9 10 11 12
4 を検索すると、6、3、4 の 3 つのヒットが得られます。log2 12 = 3 は、必要なヒット数の近似値です。
log x to base b = yの逆ですb^y = x
深さ d でサイズ n の M-ary ツリーがある場合、次のようになります。
ツリー全体をトラバース ~ O(M^d) = O(n)
ツリー内の単一パスを歩く ~ O(d) = O(log n to base M)
情報技術では、次のことを意味します。
f(n)=O(g(n)) If there is suitable constant C and N0 independent on N,
such that
for all N>N0 "C*g(n) > f(n) > 0" is true.
この表記法は、ほとんどが数学から取られたようです。
この記事には次の引用があります: DE Knuth, "BIG OMICRON AND BIG OMEGA AND BIG THETA", 1976 :
ここで議論された問題に基づいて、SIGACT のメンバー、およびコンピューター科学と数学のジャーナルの編集者が、より良い代替案が合理的にすぐに見つからない限り、上記で定義された表記法を採用することを提案します。
現在は2016年ですが、現在も使用しています。
数学的分析では、次のことを意味します。
lim (f(n)/g(n))=Constant; where n goes to +infinity
しかし、数学的な分析でも、この記号は「C*g(n) > f(n) > 0」という意味で使用されることがありました。
私が大学から知っているように、記号はドイツの数学者ランダウ (1877-1938) によって導入されました。
直感に基づく回答をお探しの場合は、2 つの解釈を提示したいと思います。
非常に広い土台を持つ非常に高い丘を想像してみてください。丘の頂上にたどり着くには 2 つの方法があります。1 つは丘の周りをらせん状に回って頂上に到達する専用の通路で、もう 1 つは階段を提供するために切り出された彫刻のような小さなテラスです。最初の方法が線形時間 O(n) で到達している場合、2 番目の方法は O(log n) です。
入力として整数を受け入れ、O(n) または theta(n) に比例する時間で完了するアルゴリズムを想像してくださいn。(ログ n) 時間。 nnumber of digits or the number of bits in the binary representation on number
分割統治パラダイムのアルゴリズムの複雑さは O(logn) です。ここでの一例として、独自のべき関数を計算し、
int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}
http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/から
ツリーの高さはルートからリーフまでの最長パスの長さであり、ノードの高さはそのノードからリーフまでの最長パスの長さであることを付け加えておきます。パスとは、2 つのノード間でツリーをたどる際に遭遇するノードの数を意味します。O(log n) 時間計算量を達成するためには、ツリーのバランスが取れている必要があります。つまり、任意のノードの子ノード間の高さの差が 1 以下である必要があります。したがって、ツリーは常に時間計算量を保証するとは限りません。バランスが取れていない限り、O(log n)。実際、最悪のシナリオでは、ツリー内の検索の時間計算量が O(n) になる場合があります。
などのバランスツリーを見ることができますAVL tree。これは、ツリーの検索中に (log n) の時間の複雑さを維持するために、データを挿入しながらツリーのバランスを取ることに取り組んでいます。