97.アルゴリズム - YukaKoshiba/MyknowledgeDocs GitHub Wiki
Algorithm @Japanese Version
Create Date：2025/01/11
Last Update Date：2025/07/01
探索系アルゴリズム : 線形探索 二分木探索 ハッシュ探索/ハッシュ法
ソートアルゴリズム : 選択ソート バブルソート マージソート
アルゴリズムとは、問題を解決するための段階的な指示の集合
=何か問題を解決したり、目標を達成したりするための手順や計算方法のこと
アルゴリズムの実行時間(Running Time)の長さを示したもの
実行時に処理するデータ量/計算量の増加により、どのように処理時間が増加するかを示す
一般的に、以下の実行時間が示されることが多い
あくまでオーダ記法は、概算の計算量を知るものであり、正確な処理時間を示すものではないが、
プログラムの効率性を測る指標となる
→効率的なアルゴリズムを選択でき、大規模なデータも高速に処理することが可能になる
- Big O Notation: アルゴリズムを実行するのに(概算)処理時間
- Big Ω Notation: アルゴリズムを実行する最速処理時間
- Big θ Notation: アルゴリズムを実行する最長処理時間
結論から言うと、より効率的なプログラムを作成して、処理時間を短くする為
アルゴリズムの処理の流れから、処理時間の大まかな時間(オーダ記法)がわかる
その為、わざわざコーディングして、処理を実行しなくても、ある程度の処理時間を推測することができる
設計段階で、代表的なアルゴリズムを知っていたり、アルゴリズムをしっかり考えていれば、
より効率的で、高レスポンスなソフトウェアの開発ができ、
より早く問題解決を行う事が出来る様になる
(余談)
最近はコンピュータメモリの集積化により、複数の処理を同時実行することが可能であるが、
まだコンピュータの性能が今ほど処理能力が高くなかった頃は、
より優れたアルゴリズムで問題解決することが、処理速度に大きく影響していた為、
プログラマはアルゴリズムを史っておく必要が今以上にあった
代表的な処理(アルゴリズム)の1つで、複数あるデータ群から目的のデータを探し出す処理手順のこと
データ群の端から1つずつ順番に探索対象であるかチェックしていく探索方法
データ群の数がn個である時、平均処理数は(1+n)/2 ≑ n/2
Ω(n/2)=1 →1番目のデータが目的のデータだった時
θ(n/2)=n →最後のデータまで目的のデータが見つからなかった時
データ群を昇順/降順に並べ替える必要が無い為、どんなデータ群でもできる一方、
上記オーダー記法に示した通り、他の探索系アルゴリズムと比較して、処理時間が長くなる
昇順/降順と規則性を持っている並べ替えられているデータ群に対して適用できるアルゴリズムで、
配列の中間にある値をチェックし、探索対象がそれよりも、大きい/小さいで切り分けていく探索方法
データ群の数がn個である時、平均処理数は(1+logn)/2 ≑ logn
Ω(logn)=1 →1番目のデータが目的のデータだった時
θ(logn)=logn →最後のデータまで目的のデータが見つからなかった時
データ群を昇順/降順に並べ替える必要があるが、
上記オーダー記法に示した様に、線形探索よりも処理時間が短い
ハッシュ関数と呼ばれる計算式を用いて、データの格納位置を参照する探索方法
ハッシュ関数でただ1つの対象データが格納されているアドレスを見つけることが出来る為、いかなる時もデータ処理数は1
Ω(1)=1およびθ(1)=1
データ格納時に同じハッシュ関数を用いた計算式で求める位置へと格納という前提条件を満たす必要があるが、
上記オーダー記法に示した様に、探索系アルゴリズムの中で最も処理時間が短い
代表的な処理(アルゴリズム)の1つで、ソートされていない値のリストを、ソートされたリストに変換する処理手順のこと
1ステップごとのソートアルゴリズムを見る
ソートアルゴリズムを可視化する
ソートアルゴリズムを可視化する
比較ベースのソートアルゴリズム
ソートされていない部分から最小/最大の要素を選択し、ソートされていない最初の要素と入れ替えることを繰り返して、配列をソートする
この処理は、配列全体がソートされるまで続けられる
n個の要素を持つ配列データを並べ替える時、
疑似コード(Pseudocode)
For i from 0 to n–1
Find smallest number between array[i] and array[n-1]
Swap smallest number with array[i]
実際のコード例:C言語
その他コード
// C program for implementation of selection sort
#include
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Assume the first element is the minimum element in the unsorted list
int min_index = i;
// Compare the second to last element and find the minimum value in the unsorted list
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
// Update min_idx if a smaller element is found
min_index = j;
}
}
// Swap the first element and the minimum value in the unsorted list
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
データ群の数がn個である時、
1回の整列ごとに未整列のデータ数が1減る為、
処理数(比較回数)は、
1回目 : n-1回 (2番目 ~ n番目 → n-2+1)
2回目 : n-2回 (2番目 ~ n-1番目 → (n-1)-2+1)
3回目 : n-3回 (2番目 ~ n-2番目 → (n-2)-2+1)
：
n-2回目 : 2回
n-1回目 : 1回
→(n-1)+(n-2)+(n-3)+…+2+1 = n(n-1)/2 = 1/2(n^2 - n) ≑ n^2
処理時間の把握の指標になるのは、O(n^2)
データ列中の隣り合う要素同士を比較し、順序があっていなければ(右のほうが小さければ)交換を繰り返して整列するアルゴリズム
1回ごとの操作で、未整列のうちの最大値または最小値が確定する
Repeat n-1 times
For i from 0 to n–2
If array[i] and array[i+1] out of order
Swap them
If no swaps
Quit
データ群の数がn個である時、
交換が必要無くなるまで、常に最初から最後まで隣同士を比較する為、
処理数(比較回数)は、
1回目 : n-1回 (1番目 ~ n-1番目)
2回目 : n-1回 (1番目 ~ n-1番目)
3回目 : n-1回 (1番目 ~ n-1番目)
：
n-2回目 : n-1回 (1番目 ~ n-1番目)
n-1回目 : n-1回 (1番目 ~ n-1番目)
→(n-1)×(n-1) = n^2 - 2n + 1 ≑ n^2
処理時間の把握の指標になるのは、O(n^2)
また、既に整列が出来ているデータセットに適用すると、
1回だけ各配列内の値を見れば良い為、Ω(n)となる
O(nlog2(n))
Ω(nlog2(n))
代表的なアルゴリズムの1つで、関数の中で自分自身を呼び出す処理手法のこと
ある問題をより小さな同じ問題に分割し、それらを再帰的に解くという考え方
- 再帰関数 : 自分自身を呼び出す関数
- 基底ケース : 再帰が終了する条件
- 再帰ステップ : 再帰呼び出しを行う部分
- スタック : 関数呼び出しの履歴を管理するデータ構造(再帰処理では特に重要)
- メモ化 : 計算結果を記憶することで、再計算を避ける手法(動的計画法など)