🆓

配列と文字列(導入)

配列と文字列

コーディング面接において最も活用されるデータ構造ではないでしょうか?配列とは、複数の値を連続的に格納するためのデータ構造です。これらの値は通常、同じ型(例えば、全て整数や全ての文字列)を持ち、それぞれが固有のインデックスまたはキーによってアクセスされます。また文字列は、文字の配列と考えることができるので、これらは同一視して考えても問題ありません。
notion image

特徴

  • 要素はメモリ上に連続して配置されます
notion image
  • 要素はメモリ上に連続して配置されているので、メモリ配置の順序にデータにアクセス(シーケンシャルアクセス)した際のキャッシュ効率を向上を期待できる(キャッシュメモリは、アクセスされたデータの近くにあるデータも一緒に読み込む傾向がある)
  • インデックスを使って任意の要素に高速にアクセスできます。これをランダムアクセスと呼びます(の時間計算量)
notion image
  • 配列のサイズは初期化時に固定され、その後は変更できません。多くのプログラミング言語では、動的なサイズ調整をサポートするために動的配列を使用することはありますが、これは裏側で新しい配列を作成し、既存の要素を新しい配列にコピーすることによって行われます。

計算量

Operation
Average Time Complexity
Worst Time Complexity
Search
Insert
Insert (at the end)
Remove
Remove (at the end)

Search(探索)

配列内の特定の要素を探す操作です。最良の場合、探している要素が最初に位置していれば、時間計算量はとなります。しかし、平均・最悪の場合(つまり、探している要素が配列の最後にあるか、存在しない場合)時間計算量は)となります。これは、N個の要素すべてを探索する必要があるためです。
notion image
Searchの擬似コード

Insert(挿入)

配列の任意の位置に新しい要素を挿入する操作です。途中の位置に要素を挿入するのは実は簡単ではありません。これは、要素を挿入するために、その位置から後ろのすべての要素を後ろにシフトする必要があるためです。最悪の場合(つまり、挿入する要素が配列の最初にある場合)時間計算量はです。
notion image
Insertの擬似コード

Insert at the end(最後に挿入)

配列の最後に新しい要素を追加する操作です。これは最良でも最悪でも時間計算量はです。これは、配列の最後はすぐにアクセス可能で、新しい要素を追加するために他の要素を移動する必要がないためです。
notion image
Insert at the endの擬似コード

Remove(削除)

配列の任意の位置の要素を削除する操作です。挿入と同様に途中の位置に要素を削除するのは簡単ではありません。これは、要素を削除した後、その位置から後ろのすべての要素を前にシフトする必要があるためです。最悪の場合(つまり、挿入する要素が配列の最初にある場合)時間計算量はです。
notion image
Removeの擬似コード

Remove at the end(最後を削除)

配列の最後の要素を削除する操作です。これは最良でも最悪でも時間計算量はです。これは、最後の要素はすぐにアクセス可能で、削除後に他の要素を移動する必要がないためです。
notion image
Remove at the endの擬似コード

動的配列(Dynamic Array)

動的配列は動的にサイズが変更できる配列です。普通の配列は静的配列でサイズが固定されており、宣言時にそのサイズを指定する必要があります。一方、動的配列は要素が追加または削除されると自動的にサイズが調整されます。
多くのプログラミング言語、例えばPython、JavaScriptなどでは配列はデフォルトで動的です。なので多くのエンジニアは配列のサイズを気にする事なく活用する事ができます。
JavaのArrayListと呼ばれるクラスがこの実装になっています。初期状態でArrayListは、一部の要素を保持するための小さな配列(デフォルトでは10要素)を確保します。新しい要素がArrayListに追加されると、その要素は内部配列に格納されます。閾値に達すると、内部的に新しい容量で新しい内部配列を作成し、古い内部配列から新しい内部配列にすべての古い要素をコピーします。
例えば擬似コードで書くと以下のような実装になっています。
このリサイズはの時間計算量となりますが、appendメソッドはの時間計算量にはなりません。何故ならリサイズは毎回行われるわけではないからです。大部分の要素の追加操作(ArrayListがまだ拡大できる場合)はO(1)です。そのため、これらの軽い操作と稀に発生する重い操作を全体として考えると、要素を追加する操作の「平均的な」時間計算量は実際にはとなります。計算量とBigOにも書きましたが、これはならし(amortized)計算量という考え方です。

Pythonでの使い方

Pythonでは配列はリストという名前で実装されています(ややこしい)。また動的配列となっているので、要素の追加や削除がされるとる配列のサイズを変更します。より詳しく知りたい方は次のPythonのデータ構造と内部実装 〜List編〜 - Qiitaをご覧下さい。
文字列はそのまま文字列型として扱います。
Pythonの文字列はイミュータブル(変更不可)であるため、一度作成した文字列は直接編集することはできません。JavaのStringBuilderのような要素はないので、listjoinを活用する事で文字列の連結時の時間計算量をにする事ができます。
 
すべてを見るには

返金は購入日から1日以内に申し出て下さい。詳細はこちらからご確認ください。
また、このコンテンツ以外の他の永久アクセス権は付与されない事はご注意下さい。

支払いはによって保護されています

購入済の方はこちらからログインしてください

Loading...