アルゴリズムとデータ構造とは何かについて解説します。
モグモグさん
技術は変化しても、変わらない基本的な部分なので重要です。
アルゴリズムの基本的なパターンを知って、それらがどう応用されているかを知り、自分のアルゴリズムの性質を判断できるようになることが大切です。
アルゴリズムとは何か
「アルゴリズム」とは、問題を解決する段階ごとの指示のことを指します。
例えば日常だとこんなアルゴリズムがあります。
- 現在地から目的地に進む道順
- 料理をするための工程やステップ
道順は、Aを通る道を選択できますし、Bを通る道を選択できますね。
また料理も先にお肉を焼くのか、野菜を切るのかなど多くの選択肢がある中で
決定していく必要があります。
このようにアルゴリズムは、プログラミングだけではなく
日常的に人間が考えていることとも言えます。
「良い」アルゴリズムをどう決めるか
それでは良いアルゴリズムとはどう判断すべきなのでしょうか？
より深く考えると「アルゴリズム解析」などが必要になってきたりするのですが
よく使われる基準としては下記になります。
- 計算速度 (速いかどうか)
- 計算精度 (正確かどうか)
- メモリ使用量 (効率的かどうか)
- プログラムの簡潔さ (簡単かどうか)
その中でも計算速度は選択によって大きく差がつきやすいです。
O記法
計算速度には、O記法が使われます。
O記法は、データ件数に対して繰り返しの増加を求めたものです。
例えばn個のデータに対して繰り返し回数がnに比例する場合は、O(n)と書きます。
O(1)の場合は、データの数nに関わらず計算量は変わらないままを表します。
O(log n) nが2倍、3倍と増えても、計算量は2, 3と増えることを表します。
O(n log n) O(log n) にnの計算量がかけられたものを表す。
logとは、Xを何乗すればYになるかというものです。
このように O記法を用いて計算速度を評価していくことができます。
データ構造とは
続いてデータ構造について説明していきます。
データ構造とは、データを効率的に使用できるようにデータを格納し、組織化する方法のことです。
一般的なデータ構造には、
- 配列
- ファイル
- 連結リスト
- スタック
- キュー
- ツリー
- グラフ
などがあります。
どのような処理を行うのかを考えて、最適なデータ構造を選択する必要があるのでそれぞれの特徴を知り選択できるようになっておく必要があります。
例えば配列であれば特徴としては
- インデックスにより高速にアクセスが可能であり、末尾のデータ挿入や削除が高速
- しかし、データが大きい場合にメモリを多く消費する
などがあります。
このようにデータ構造を最適に選択していくことはアルゴリズム同様大切です。
まとめ
今回はアルゴリズムとデータ構造はこういうものだと理解していただければと思います。
具体的な解説は他の記事で行いますので気になる方は合わせて読んでみてください。
