アルゴリズムとプログラミング｜エンベデッドシステムスペシャリスト試験

データが増えると手間はどう増えるか、何を渡すか

探索の手間は、データの個数が増えたときにどう伸びるかで比べます。先頭から順に調べる線形探索では、調べる回数は個数に比例して増えます。整列済みのデータを半分ずつに絞る二分探索では、個数が倍になっても回数は一回ほどしか増えません。

ハッシュ表は、キーからハッシュ関数で格納位置を計算し、その位置を直接参照します。異なるキーが同じ位置になる衝突が起きなければ、位置を一度計算して一か所を見るだけで済むので、データ1個当たりの探索時間は表の中の個数によらず一定です。グラフにすれば横軸に平行な直線になります。実際には衝突が起きると、その分だけ余分な手間がかかります。

サブルーチンへの引数の渡し方は、渡すものが値の写しか、変数の場所かで分けます。値呼出しは値をコピーして渡すので、呼ばれた側で仮引数を書き換えても呼出し元の変数は変わりません。参照呼出しは変数の場所を渡すので、呼ばれた側の変更がそのまま元の変数に及びます。

ほかに、終了時に仮引数の値を呼出し元の変数へ書き戻す結果呼出しや、引数の式そのものを渡して使うたびに評価する名前呼出しがあります。呼出しの後で元の変数が変わり得るかどうかを考えると、方式ごとの性質を整理できます。