📝

アルゴリズムとデータ構造について

2021/12/31に公開

アルゴリズムとは

→ 料理で例えると、「調理手順」
→ 問題を解決するための手順や計算方法

アルゴリズムを多く知っていれば、より多くの問題をスムーズに解決することができる。
アルゴリズムを記述するための図として、フローチャートがよく用いられる

この３つの処理を組み合わせて処理の流れを記述することを、構造化プログラミング と呼ぶ

ある処理がアルゴリズムとなるためには、2つの重要な条件(正当性と停止性)をクリアする必要がある

アルゴリズムは、「指定された条件を満たす入力が与えられた場合、必ず正しい結果を導き出すことを保証する」 ことが必要で、これを 「アルゴリズムの正当性」 と呼ぶ

正当性は、アサーションという手法で検証ができる。
アサーションとは、アルゴリズムの手順の中の任意の位置で、その時点において満たさなければいけない条件や結果がが正しいかどうかを細かく判定すること を言います。

アルゴリズムは、最終的に必ず停止する必要がある。
「アルゴリズムの停止性」は、「いかなる条件の入力値が与えられた場合でも、有限時間内に必ず正しく停止することを保証する」 ことで示される。

処理が終わらない手順のことは、無限ループと呼ばれ、アルゴリズムとはなりえない。

→ 料理で例えると、「焼肉定食」「魚定食」など（それぞれ主菜・副菜・主食・汁物があるとする）
→ データの集まりをコンピューターの中で効率的に扱うため、一定の形式で格納したもの

特定の問題を解く手順（アルゴリズム）には、それぞれに適したデータ構造がある。

データのグループ分けのことをデータ型といい、
データの具体的な値を値という

名前	内容
配列	同じ種類のデータを複数並べたデータ構造を配列という。大きさなどはあらかじめ固定されている。
リスト	同じ種類のデータに順序付けして並べたデータ構造をリストという。
スタック	机に本を積み重ねていくように、データを管理する方法。データを入れた順序と逆順にデータを取り出すことができるのが特徴
キュー	スタックとは逆に、データを入れた順に取り出すことができるデータ構造
ツリー構造	一つの要素（ノード）が複数の子要素を持ち、一つの子要素が複数の孫要素を持ち、という形で階層が深くなるほど枝分かれしていく構造のこと。
ヒープ構造	親要素が子要素より常に大きい（あるいは小さい）という条件を満たすもの。