アルゴリズムとプログラミング配列操作（挿入）

要素数 n の配列の先頭（インデックス0）に新しい要素を挿入するとき、既存要素の移動回数として正しいものはどれか。ただし配列のサイズは十分に確保されているものとする。

ア.0回（移動不要）

イ.1回

ウ.n/2 回

エ.n 回正解

解説

配列の先頭への挿入は「電車の先頭に割り込む」ようなもの。後ろの乗客全員が一席ずつ後ろにずれなければならない。n 人いれば n 回のシフトが必要になる。

なぜエが正解か

配列の先頭（インデックス0）に要素を挿入するには、既存の全 n 要素をそれぞれ1つ後ろのインデックスにシフトする必要がある。インデックス n-1 から順に 0 まで後ろ向きにずらすため、移動回数は n 回となる。これが配列先頭挿入の計算量が O(n) となる理由である。

なぜアは間違いか

連結リストの先頭挿入なら O(1) で移動不要だが、配列は連続メモリ領域のため全要素のシフトが必要。配列と連結リストの特性を混同した誤り。

なぜイは間違いか

1回の移動で済むのは配列の末尾への追加。先頭への挿入と末尾への追加を混同した誤り。

なぜウは間違いか

中間位置への挿入のイメージから n/2 と答えてしまう誤り。先頭への挿入は最悪ケースであり、全 n 要素のシフトが必要。

出典: AI生成問題（学習用）

← 前の問題

次の再帰関数 f(n) を f(4) として呼び出したとき、返り値はどれか。 ``` function f(n): if n <= 1: return 1 return n * f(n - 1) ```

次の問題 →

n 個の要素を持つ整列されていない配列から、線形探索（逐次探索）で特定の値を探すときの平均比較回数として最も適切なものはどれか。ただし探索する値は必ず配列中に存在するものとする。