アルゴリズムとデータ構造~配列(array)~
配列とは
同じ型のデータを決まった数だけ保存したものです。この「決まった数」というのが重要で、決まった数以上のデータを詰め込もうとすると、データは記憶されません。ここの位置を決めて、番地さえ入れればアクセスできます。これはランダムアクセスが可能になっているということです。
計算量
配列の要素の個数をnとします。番号を指定すればその箱の中にある要素を参照する操作はO(1)です。マンションやアパートで、その号室のインターフォンをならせば、中にいる人が出てきてくれるって感じです。挿入と削除に関しては少し厄介です。配列にデータを入れるときに、すでに入っているデータを一つずつずらしてスペースを空けて、データをいれないといけないのです。削除も同じで、空いたところがなくなるようにずらさないといけません。ともにO(n)です。
配列の利点、不利な点
データの参照は、番号さえいれれば中身の要素を参照できるので、とても有利です。しかし、データの削除や挿入は位置関係をずらす必要が出てくるので、これらの操作には向いていません。配列の中のデータの並びが適当でよい場合は、挿入はO(1)でできるが、こういった配列は基本的に汎用性がかなり低いので、あまり考えません。また、配列に入れられる個数はあらかじめ宣言しているので、余分に確保してしまうと、メモリが無駄になり、確保が少なすぎるとデータがあふれて記憶されません。プログラミングを学んでいるときにはあまり気にはならないと思いますが、ゲームやシステムを作る立場になると、とても細心に扱わなければなりません...。
