同じ問題でも、手順で大違い
前レッスンで、アルゴリズム(手順)には良し悪しがあると述べました。その良し悪しの、最も重要な尺度が効率——専門的には計算量です。驚くべきことに、同じ問題を解くのでも、使う手順によって、必要な手間が桁違いに変わることがあります。この「効率」の感覚は、コンピュータの世界だけでなく、あらゆる問題解決や仕事の段取りに生きる、重要な思考です。
電話帳で名前を探す
分かりやすい例で考えましょう。分厚い電話帳(五十音順に並んでいる)から、ある名前を探すとします。二つの手順を比べてみます。
- 手順A(先頭から順に):1ページ目から、1つずつ順番に探していく。運が悪ければ、最後のページまで全部見ることになる
- 手順B(半分に絞る):まず真ん中を開く。探す名前がそれより前か後かで、探す範囲を半分に絞る。また真ん中を開き、また半分に絞る……これを繰り返す
どちらも同じ「名前を探す」問題ですが、効率がまるで違います。名前が100万件あったとして、手順Aは最悪100万回見る必要があります。ところが手順Bは、半分ずつ絞るので、わずか20回程度で見つかります(100万を半分にし続けると、約20回でたどり着く)。100万回と20回——これが、手順による計算量の、桁違いの差です。私たちが辞書を引くとき、無意識に手順Bを使っているのは、それが圧倒的に効率的だからです。
データが増えると、差が爆発する
計算量の考え方で、最も重要なのが、データが大きくなったときの振る舞いです。データが少ないうちは、非効率な手順でも、たいして困りません。しかし、データが増えると、手順による差が爆発的に開きます。
先の例で、名前が10件なら、手順Aでも10回、手順Bでも数回。大差ありません。しかし、100万件になると、100万回対20回。10億件なら、10億回対30回。データが増えるほど、非効率な手順は、指数的に手間が膨らみ、やがて現実的な時間では終わらなくなるのです。膨大なデータを扱う現代では、この「大きくなったときの効率」が、決定的に重要になります。検索エンジンが、膨大なウェブから一瞬で結果を返せるのは、効率的なアルゴリズムのおかげなのです。逆に、非効率なアルゴリズムでは、どんなに高性能なコンピュータでも、間に合いません。
効率の感覚を、日常に
計算量の考え方は、日常の段取りにも生きます。「同じことをするのに、もっと効率的な手順はないか」「この方法は、量が増えても大丈夫か」——こう問う習慣が、無駄を減らします。たとえば、大量の書類を分類するとき、一枚ずつ全部を見比べるより、まず大きく仕分けてから細かく分ける方が効率的です(手順Bの発想)。仕事や生活の中の「非効率な繰り返し」に気づき、より良い手順を設計する。これは、アルゴリズム的思考が与える、実践的な力です。
同時に、限界も知っておきましょう。世の中には、どんなに効率的な手順を工夫しても、本質的に「解くのに膨大な手間がかかる問題」も存在します(計算の難しさには限界がある)。これは、数学の証明の限界やカオスの予測の限界と同じく、「できることには限界がある」という、知の謙虚さにつながります。
ニュースで使う視点
処理速度、効率化、大規模データ、AIの計算コスト——効率や計算に関わるニュースを読むときは、「データが増えたときに、その手順は耐えられるか」「効率の差が、何を可能にし、何を不可能にしているか」を意識してください。次のレッスンでは、問題を解く前提となる——問題の分解(計算論的思考)を見ます。