計算オーダー
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/13 01:36 UTC 版)
「配列」という語は、抽象データ型というよりも、添え字をオフセットとしてメモリのアドレスにマップすることで、Ο(1) でアクセスできる具象あるいは実装を特に指す場合がある（その意味では、次節の連想配列などは「配列」ではない、ということになる）。 配列に要素を挿入／削除する際、要素間に「隙間」が無いようにするには、線形リストと異なり、挿入／削除位置から後ろの領域にあるすべてのデータの移動（コピー）が必要となる。そのため、挿入／削除にO(n)時間かかる。さらに配列は連続領域を必要とするため、挿入時に領域が不足した場合に拡張する際のメモリ再確保のコストが高い。 探索は一般的には線型探索になるためΟ(n)だが、データがソート済みであれば二分探索を使うことでΟ(log n)に軽減することもできる（抽象データ型としては、sorted array などの名前で別のデータ構造と考える場合もある。en:Sorted array を参照）。
※この「計算オーダー」の解説は、「配列」の解説の一部です。
「計算オーダー」を含む「配列」の記事については、「配列」の概要を参照ください。
ウィキペディア小見出し辞書の「計算オーダー」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 計算オーダーのページへのリンク
