実装問題

アルゴリズムやデータ構造を扱うとき、人はしばしばそれらがとても複雑で難解だという先入観を持ちがちです。しかし実際には、多くの場合、シンプルで直感的なものです。肝心なのは、アルゴリズムがどのように動作するかをしっかり掴むために、ある程度の練習と実際に手を動かして経験を積むことです。

具体的な問題や演習を解いていると、ある問題群や問題のカテゴリーが共通の特徴を持っていることに気づくでしょう。これにより、同じテクニックをまとめて適用できるグループがいくつか存在するのです。

そのうちの一つが「実装問題」です。これらの問題は、解法に必要な手順が問題文にすでに書かれていることが多いのが特徴です。つまり「プログラムがどんな手順を踏めばよいか」は問題文に記載されているため、ソフトウェアエンジニアとしては、示された手順を最適に実装し、求められる結果を得ることが主な課題になります。しかし、問題文に手順が示されているからといって、必ずしもすぐに実装方法が明確になるとは限りません。

チャレンジ - Find the missing number

1から n までの数字がすべてそろっているはずなのに、1つだけ抜けているとき、その「欠けている数字」を探す問題です。

入力

最初の行に整数 n (2 ≤ n ≤ 100 000) が与えられます。

次の行には n-1 個の整数 (1 ≤ ≤ n) がスペース区切りで与えられます。

出力

欠けている数字を出力してください。

例

複雑さとビッグ表記法のチュートリアル

一見すると、上記の問題は簡単そうですが、素朴な（ナイーブな）方法ではテストケースをすべて通過するほど速く動作しないかもしれません。

素朴なアプローチとしては、入力された要素をリストに読み込み、1 から n までの数字をすべてチェックし、その数字がリストに含まれていなければ答えとする、という方法が挙げられます。たとえば次のようなイメージです:

n = int(input())
a = [int(ai) for ai in input().split()]

for i in range(1, n + 1):   # n 回の操作
    if i not in a:          # n 回の操作（全ての要素を走査）
        print(i)            # 解答が見つかりました！

このアルゴリズムは非常に遅く、1 から n までのすべての数をチェックし、さらにそのたびにリスト全体をなめて「含まれているかどうか」を確認しているため、要素数が n に近いリスト検索が n 回繰り返されます。リスト内に特定の要素があるかどうかを確認するには、線形時間、つまりリストの要素を一つずつ調べる必要があるため、最終的にはおよそ 回の操作が行われることになるのです。

この問題では n が最大で10万まであり、アルゴリズムは最大で 、つまり100億回の操作を行うことになります。一般的なコンピュータでは約100秒かかる計算量なので、制限時間が1秒という条件では到底間に合いません。したがって、もっと効率的な解決策が必要になります。

Big Notation

ビッグオー記法（Big O notation）は、入力サイズが大きくなるにつれてアルゴリズムの実行に必要な時間や操作回数がどのように増加するか、その上限を示す数学的記法です。アルゴリズムが入力のサイズに対してどれほど多くの処理を行うのか、おおまかな目安を示してくれます。

今回の問題では、素朴な方法を使うと ~ 回の操作が必要になると推定できました。したがって、そのアルゴリズムの計算量は と表せます。

このトピックについてはコースの後半でより直感的かつ理論的に詳しく解説していきます。