[解決済み] O(log n)とは具体的にどのような意味ですか？

質問

Big O記法の実行時間と償却時間について学習中です。 の考え方は理解しています。 O(n) 線形時間とは、入力の大きさがアルゴリズムの成長に比例して影響することを意味します。 O(n ² ) などなど、順列生成器のようなアルゴリズムでも O(n!) 回、階乗で増えていく。

例えば、次のような関数があります。 O(n) なぜなら、アルゴリズムは入力に比例して成長するからです。 n :

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

同様に、ネストされたループがあった場合、時間はO(n ² ).

しかし、具体的にどのような O(log n) ? 例えば、完全な二分木の高さは、どういう意味かというと O(log n) ?

Logarithmが何であるかは（あまり詳しくはないかもしれませんが）知っています。 <サブ 10 100＝2ですが、対数時間を持つ関数の同定方法がわかりません。

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

対数時間による関数の同定方法がわかりません。

対数実行時間関数の最も一般的な属性は、次のとおりです。

• あるアクションを実行するための次の要素の選択が、いくつかの可能性のうちの1つであること。
• を1つだけ選択する必要があります。

または

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

そのため、例えば電話帳で人を探すのはO(log n)なのです。を確認する必要はない。 あらゆる その代わりに、名前のアルファベット順の位置から探すことで、単純に分割統治することができ、最終的に誰かの電話番号を見つけるまでに、各セクションの部分集合を探索する必要があるだけです。

もちろん、電話帳が大きくなっても時間はかかりますが、追加されたサイズに比例して急激に大きくなるわけではありません。

電話帳の例を発展させて、他の種類の操作の比較や その の実行時間です。ここでは、電話帳に ビジネス (イエローページ)は、一意な名前と 人 (ホワイトページ)は、一意の名前を持たない場合があります。電話番号は、最大でも1人の個人または企業に割り当てられます。また、特定のページをめくるのに一定の時間がかかると仮定します。

電話帳に対して行うであろういくつかの操作の実行時間を、速いものから順に並べてみました。

• O(1)(最悪の場合)。 あるビジネスの名前が載っているページとビジネス名が与えられたら、電話番号を見つけなさい。

• O(1)(平均的な場合)です。 ある人の名前が入っているページとその人の名前が与えられたら、電話番号を求めなさい。

• O(log n)である。 人名が与えられたとき、まだ検索していない本の部分の約半分の位置をランダムに選び、その位置に人名があるかどうかを調べて、電話番号を見つける。そして、その人物の名前がある部分の約半分まで同じことを繰り返す。(これが人名の2値検索である）。

• O(n)です。 電話番号に数字の "5" が含まれる人をすべて探しなさい。

• O(n)です。 電話番号が与えられたら、その番号を持つ人物や企業を探す。

• O(n log n)である。 印刷所で手違いがあって、うちの電話帳は全部のページがランダムな順番で挿入されているんだ。各ページの最初の名前を見て、そのページを新しい空の電話帳の適切な場所に置くことで、順序を正しく修正する。

以下の例では、今、印刷所に来ています。電話帳はそれぞれの住民や会社に郵送されるのを待っており、それぞれの電話帳には郵送先を示すステッカーが貼られています。電話帳は1人または1事業所に1冊ずつ配られます。

• O(n log n)である。 電話帳をパーソナライズしたいので、指定されたコピーから各個人や企業の名前を探し出し、電話帳の中でその名前を丸で囲み、ご愛顧に感謝する短い文章を書きます。

• O(n ² ): 会社でミスがあり、各電話帳の電話番号の末尾に"0"が余分についています。ホワイトアウトで0を消してください。

• O(n - n!)です。 電話帳を出荷ドックに積み込む準備が整いました。残念なことに、本を積むはずのロボットがおかしくなってしまったのだ。さらに悪いことに、すべての本をトラックに積んでから、順番が正しいかどうかを確認し、正しくない場合は本を降ろしてやり直すのです。(これは恐ろしい ボゴソート .)

• O(n ⁿ ): あなたはロボットを修理して、正しく物を積めるようにしました。翌日、同僚の一人があなたにいたずらをし、搬入口ロボットを自動印刷システムに接続しました。ロボットがオリジナルの本を積み込もうとするたびに、工場の印刷機がすべての電話帳を複製してしまうのです。幸い、ロボットのバグ検出システムは高度なもので、積み込み用の複製本を見つけたときにさらに印刷しようとすることはありませんでしたが、それでも印刷されたすべてのオリジナル本と複製本を積み込まなければならないのです。