アルゴリズム
アルゴリズムとは問題を解決するための計算や処理の手順。またアルゴリズムは正しいこと、そして設計(効率性)も求められる。コードの質だけではなく、パフォーマンスの質も考える。
実行時間表記
アルゴリズムやコードの実行時間を表す表記が存在する。
実行時間の上限・・・O オーダと読む。
- O(n^2)
- O(n log n)
- O(n)
- (一度に1ページずつ順番に検索する場合)
- O(log n)
- (電話帳を毎回半分にする場合)
- O(1)
- 問題の大きさに関係なく、一定数の手順を実行するアルゴリズムの場合
実行時間の下限・・・Ω オメガと読む。
実行時間の上限と下限が同じ場合・・・θ シータと読む。
ランダムな数字の配列から特定の値(今回は0)を見つける場合のアルゴリズム
線形探索
最も単純な値を1つずつチェックするやり方。
for i from 0 to n - 1 配列の中身の数分回す
if number behind i'th door 求めている数値が存在するか確認
return true 存在すれば真を返す
return false 無ければ偽を返す
実行時間の上限はO(n) n回1つずつ確認するから
下限はΩ(1) 1つ目で見つかる場合二分探索 バイナリーサーチ
If no doors ドアがあるか確認
Return false なければ偽を
If number behind middle door 真ん中のドアの値を確認
Return true 存在すれば真を
Else if number < middle door 真ん中のドアより手前にある場合
Search left half 左半分を探す
Else if number > middle door 真ん中のドアより奥にある場合
Search right half 右半分を探す
実行時間の上限はO(log n) n回1つずつ確認するから
下限はΩ(1) 検索している値が中央で見つかる場合アルゴリズムの効率性で大事なのは『何を繰り返し実行しているか』
データ構造
c言語では独自の構造体を作ることができる。typedefとstructを使用する
#include <stdio.h>
#include <string.h>
typedef struct
{
string name;
string number;
}
person;
int main(void)
{
person people[2];
people[0].name = "David";
people[0].number = "+1-400-34934-4839";
people[1].name = "Carter"
people[1].number = "+1-617-495-1000";
}カプセル化・・・関連する情報の断片を封じ込めること。
ソート
選択ソート
- 未ソート部分の中から最小値（または最大値）を見つけ、その値を未ソート部分の先頭と交換する。
- 未ソート部分の先頭を増やし、これを繰り返す。
For i from 0 to n–1
Find smallest item between i'th item and last item
Swap smallest item with i'th itemバブルソート
- 隣接する2つの要素を比較し、順序が逆であれば交換する。
- 全体の配列の末尾まで1回の走査を行う。この操作により、最大の要素が配列の最後に移動する。
- 未ソート部分の要素が残っている間、1～2の操作を繰り返す。
Repeat until sorted
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them再帰
再起とは関数が自身を呼び出す機能。
ベースケース・・・再起処理を行う時に、永遠に呼び続けないようにするためのコード。値が存在するかなどの条件分岐。
マージソート
- 分割（Divide）：ソートされていないリストを半分に分割します。この操作を再帰的に行い、各部分リストが1つの要素になるまで分割します。
- 統合（Merge）：分割した部分リストを再帰的にマージして、ソートされた部分リストを作成します。マージ操作では、2つのソートされた部分リストをマージし、新しいソートされた部分リストを作成します。
マージソートは選択ソートやバブルソートよりも高速な場合があるが、メモリを多く消費する。
If only one number
Return
Else
Sort left half of number
Sort right half of number
Merge sorted halves以下は実行時間表記のまとめ
オーダ
- O(n^2)
- 選択ソート、バブルソート
- O(n log n)
- マージソート
- O(n)
- 線形探索
- O(log n)
- バイナリ検索
- O(1)
オメガ
- Ω(n^2)
- 選択ソート
- Ω(n log n)
- マージソート
- Ω(n)
- バブルソート
- Ω(log n)
- Ω(1)
シータ
- Θ(n2)
- 選択ソート
- Θ(n log n)
- マージソート
- Θ(n)
- Θ(log n)
- Θ(1)
