アルゴリズム

本レポジトリのアルゴリズム実装例は下記の通りである．

数学

ユークリッドの互除法(Euclidean algorithm)

[code], [wiki]

ニュートン法(Newton's method)

[code], [wiki]

探索

線形探索(Linear search)

n 個のデータから 1 個のデータを探索する場合，比較回数は高々 n 回である．最悪計算時間は，O(n)．

[code], [wiki]

二分探索(Binary search)

n 個のデータから 1 個のデータを探索する場合，比較回数は高々 log2(n)+1 回である．最悪計算時間は，O(log n)．

[code], [wiki]

ソート

バブルソート(Bubble sort)

比較回数は，高々 n(n-1)/2 回である．最悪計算時間は，O(n^2)．

[code], [wiki]

選択ソート(Selection sort)

比較回数は，高々 n(n-1)/2 回である．最悪計算時間は，O(n^2)．

[code], [wiki]

挿入ソート(Insertion sort)

比較回数は，高々 n(n-1)/2 回である．最悪計算時間は，O(n^2)．

[code], [wiki]

分布数え上げソート(Counting Sort)

最悪計算時間は，O(n+k)．なお，各要素が[min, max]内である場合 k=max-min である．

[code], [wiki]

クイックソート(Quicksort)

比較回数は，高々 n(n-1)/2 回である．最悪計算時間は，O(n^2)．

[code], [wiki]

マージソート(Merge sort)

[code], [wiki]