私はビッグ O 表記法の実行時間と償却時間について学んでいます。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という意味で対数が何であるかを（あまり詳しくないかもしれませんが）知っていますが、対数時間を持つ関数を識別する方法が理解できません。
ベストアンサー1
ログ時間で関数を識別する方法がわかりません。
対数実行時間関数の最も一般的な属性は次のとおりです。
- 何らかのアクションを実行する次の要素の選択はいくつかの可能性のうちの1つであり、
- 選択する必要があるのは 1 つだけです。
または
- アクションが実行される要素はnの数字である
たとえば、電話帳で人を検索するのにかかる時間は 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 人がいたずらをして、積載ドック ロボットを自動印刷システムに配線します。ロボットがオリジナルの本を積載するたびに、工場のプリンターがすべての電話帳を複製します。幸い、ロボットのバグ検出システムは十分に洗練されているため、ロボットは、積載する複製本に遭遇しても、それ以上のコピーを印刷しようとはしません。ただし、印刷されたオリジナルの本と複製本はすべて積載する必要があります。