この記事は東京海洋大学NePPのAdvent Calendar 2024の12日目です🎁
はじめに
アルゴリズムやデータ構造を一通り学習して浮かぶ疑問がありますね。
「計算量とかって何の役に立つの？🤔」
いきなり学ぶ計算量とかいう概念、これはアルゴリズムやデータ構造を使用しようという場面において選択の軸となることがあります。
いつか来るかもしれないそのような機会のために、この記事では、アルゴリズムやデータ構造を選ぶ際の評価軸となることをまとめています。最初に観点を示したのちに簡単な説明が続きます。
選択する際の観点
- 時間計算量
- 空間計算量
- 取り扱うデータのサイズ
- データのアクセス・挿入・削除・更新の頻度
簡単な解説
時間計算量
問題解決に要する所要時間のこと。よくオーダー記法で表される。
小さいほうがよい。
競技プログラミングでは時間計算量に注目することが多い気がする。
空間計算量
問題解決のプログラムを書くために必要なメモリ容量のこと。
小さいほうがよい。
取り扱うデータのサイズ
入力が使うメモリ容量のこと。
オーダー記法ではNで表される。
時間計算量に影響を与える場合もあれば、与えないこともある。
データへのアクセス・挿入・削除・更新の頻度
実際の使用状況による。
データ構造によってそれぞれにかかる時間が異なる。
ひとりごと
大学の実験で計測センサーを取り扱った際にこのようなことを言われました。
「センサーに必要な精度は使用用途によって変化します。
例えば、電車でどの線に乗っているかを知りたいときには1~2mの誤差に収めないといけませんが、大学に来ていることを知りたいときには20mの誤差があっても許されるのです。
技術者は誤差をなくそうと奮闘しがちですが、本当に必要なことはどの程度の精度が必要なのかに関して使う人と技術者が共有しあうことなのかもしれないですね。」
これはコードを書く人（技術者）とユーザにも通じることだと思います。
高速化をめざしてコードを書こうとしてしまうことが多々ありますが、実際に使う状況を考えることも忘れないようにしたいと思いました。
最後に
今回が初めての記事となりましたが、脳内の考えを整理することができるという点で記事を書くことのメリットを感じることができました。最後になりますが、このような視点を学ぶきっかけをくださったSTEP関係者のみなさまにこの場で感謝を申し上げます。