arrays - ソート済み配列 Big o表記

Question

簡単な質問があります。並べ替えられた配列のビッグ O 表記が O(log N) なのはなぜですか? ソートされた配列になります。

Answer 1

質問はやや偽物です。複雑さは配列には適用されませんが、実際には配列をソートするアルゴリズムに適用されます（メモリではなく実行時の複雑さを意味すると思います）。

したがって、使用するアルゴリズムに応じて、配列をソートするためのO（X）のXは大きく異なる可能性があります。

これらのページをチェックして、一般的な複雑さおよび特殊なケースの配列ソートの開始点を確認してください。

アルゴリズムの複雑さの概要

配列の並べ替え：アルゴリズムと効率

ウィキペディア：計算の複雑さの理論

Answer 2

Big O表記は、通常、アルゴリズムのコンテキストで意味があります。Big O表記がO（log n）であると言うとき、どのような操作を検討していますか。

検索を意味する場合は、二分探索を使用できるため、O（log n）になります。これは基本的に、配列の中央の要素を見て、それが検索している要素よりも大きい場合は、大きい方の半分を（同じ方法で）検索し、その逆も同様です（まだ行っていない場合）。もちろんあなたの要素を見つけました）。ウィキペディアでより詳細な説明を読むことができます。

検索の各ステップ（中央の要素を探す）で、検索する必要のある配列のサイズを半分に減らします。これで、検索要素が中央の要素のどちら側にある必要があるかがわかるようになります。もちろん、これはソートされた配列でのみ機能します。ソートされていない配列の場合、使用できる検索アルゴリズムは線形検索のみです。線形検索では、平均n/2の検査を受ける配列内のすべての要素を調べます。

一般に、Big Oはアルゴリズムの実行時の特性を表すため、ソートされた配列のBig Oとは何かを尋ねることはできません。これは、配列に対する何らかの操作である必要があります。ただし、一部のデータ構造が占めるスペース（メモリ）の観点からBigOを考慮することができます。この場合でも、ソートされた配列はN個の要素を格納するためにO（n）スペースを必要とします。