アルゴリズムとデータ構造

コンピュータで行う計算の手順をまとめたものをアルゴリズムといい、データを格納する方法をデータ構造といいます。同じ数学の問題を解く方法がいくつもあるように、同じ計算を行うアルゴリズムや、同じ機能を提供するデータ構造は複数あります。全く同じ計算を行うアルゴリズムであっても、片方は計算に1時間かかるがもう一方は1秒でできるということがよくあります。アルゴリズムとデータ構造では、同じ計算を行う場合でも、どのようにすればより高速に計算ができるかということについて考えます。

オーダー記法

全く同じアルゴリズムであっても、実装の仕方(たとえばC言語で実装するかPythonで実行するか)や実行するコンピュータ(たとえばパソコンで実行するかスーパーコンピューターで実行するか)によって実行時間が変わってきます。どこどこのコンピュータでPythonで実装したら10秒だった、と言われてもそれがどのくらい早いのかピンと来ないし、数学的な取り扱いにも不便です。

アルゴリズムの分野では、計算の早さを秒数ではなく、全体の計算に必要な基本操作の回数ではかります。

しかし、操作の回数ではかっても数え方や書き方によってブレが出てしまいます。そこで、具体的な操作回数ではなく、回数をざっくり表したオーダー記法というものを使ってはかります。オーダー記法を使うと、細かい定義の差や実装の方法に囚われることなく計算の効率を表すことができます。オーダー記法について学び、アルゴリズムの計算時間のオーダーを自分で導けるようになるのがアルゴリズムとデータ構造の大きな目標です。

まとめ

コンピュータの計算手順のことをアルゴリズムといい、アルゴリズムによって実行速度が異なります。アルゴリズム分野ではオーダー記法という方法で実行速度を数学的に記述し、オーダー記法を証明できるようになることがこの講義の目標になります。