整列済み二次元配列を探索する計算量を求める

解説

この関数は、n 行 m 列の整列済み二次元配列の右上隅（row=1, col=m）から探索を開始する「階段探索」と呼ばれるアルゴリズムである。 【動作の仕組み】 ・A[row, col] = target ならば探索成功で true を返す。 ・A[row, col] < target ならば、現在の行には target より大きい値しかないため、行を 1 つ下に進める（row ← row + 1）。 ・A[row, col] > target ならば、現在の列には target より小さい値しかないため、列を 1 つ左に進める（col ← col - 1）。 【計算量の導出】 while ループの各繰返しでは、row が 1 増えるか col が 1 減るかのいずれかが必ず起こる（target が見つかった場合は即座に return する）。row は 1 から始まり最大で n+1 になるまで増加でき（最大 n 回）、col は m から始まり最小で 0 になるまで減少できる（最大 m 回）。したがって、ループの実行回数は高々 n + m 回であり、各繰返しの処理は定数時間 O(1) であるから、全体の最悪時の時間計算量は O(n + m) である。 【具体例によるトレース】 3 行 4 列の配列 A = {{1,3,5,7},{2,4,6,8},{3,5,7,9}} で target=0（存在しない値）を探す場合: row=1, col=4: A[1,4]=7 > 0 → col=3 row=1, col=3: A[1,3]=5 > 0 → col=2 row=1, col=2: A[1,2]=3 > 0 → col=1 row=1, col=1: A[1,1]=1 > 0 → col=0 col < 1 でループ終了 → false を返す（4 回） target=9.5 を探す場合: row=1, col=4: 7 < 9.5 → row=2 row=2, col=4: 8 < 9.5 → row=3 row=3, col=4: 9 < 9.5 → row=4 row > 3 でループ終了 → false を返す（3 回） ジグザグに進む最悪ケース（target=4.5）: row=1, col=4: 7 > 4.5 → col=3 row=1, col=3: 5 > 4.5 → col=2 row=1, col=2: 3 < 4.5 → row=2 row=2, col=2: 4 < 4.5 → row=3 row=3, col=2: 5 > 4.5 → col=1 row=3, col=1: 3 < 4.5 → row=4 ループ終了（6 回 = n + m = 3 + 4 - 1）

選択肢ごとの解説

ア

行方向と列方向のそれぞれに二分探索を行っていると誤解した場合にこれを選ぶ。実際には二分探索は行われておらず、各ステップで行か列を 1 ずつ移動している。

イ

短い方の次元の長さで探索が終わると誤解した場合にこれを選ぶ。実際には行と列の両方向に移動するため、短い方だけでは済まない。

ウ

移動回数が大きい方の次元で抑えられると考えた場合にこれを選ぶ。行の移動回数と列の移動回数はそれぞれ独立に n 回、m 回まで発生しうるため、合計は n + m になる。

エ

正解。while ループの各繰返しで row が 1 増えるか col が 1 減るかのどちらかが必ず起こる。row は最大 n 回増加し、col は最大 m 回減少するため、ループの実行回数は高々 n + m 回である。

オ

n 行のそれぞれに対して二分探索を行う別のアルゴリズムと混同した場合にこれを選ぶ。この関数は各行で二分探索を行っているわけではない。

カ

最悪の場合にすべての要素を調べると誤解した場合にこれを選ぶ。各ステップで行か列を一方向にしか進まないため、全要素を訪問することはありえない。

キ

計算量に対数の係数が掛かると誤解した場合にこれを選ぶ。整列済みであることから対数的な要素が加わると考えがちだが、この関数は毎回定数時間の比較で 1 マス移動するだけであり、対数は現れない。

登録すると解いた結果が残り、間違えた問題は日をおいて復習に出ます。