挿入ソート(Insertion Sort)
挿入ソートとは、安定な内部ソートのアルゴリズムの一つです。小さい要素を前に「挿入」するために、他の要素を前に1つずつ前にずらしていきます。
既にソートされた配列の後ろに、いくつか要素を追加してソートしたい時に ...
バブルソート(Bubble Sort)
バブルソートは安定なソートアルゴリズムの一つです。隣り合う要素の大小関係を見て、入れ替えながらソートしていきます。
他のソートには最悪計算時間が\(O(nlogn)\)のものもありますが、バブルソートの計算 ...
選択ソート(Selection Sort)
ソートアルゴリズムの中でも、最も基本的なアルゴリズムの一つです。配列の中から最小値や最大値を探して、先頭や最後尾と入れ替えながらソートしていきます。
他のソートには計算量が \(O(nlogn)\) のものも ...
二分探索(Binary Search)のアルゴリズム
二分探索とは、ソート済みである配列の中から、目的の値が存在するかを調べる探索アルゴリズムです。高速でわかりやすいため非常に良く使われます。
線形探索はソートしていない配列でも探索することができます。二分 ...
ビット全探索（ 2^n 通りの全探索）
bit演算を上手く用いると、それぞれの要素に対して「使うか」「使わないか」の2通りがあるような、\(2^n\) 通りの場合を全探索することができます。
言い換えると、集合 \(\{0,1,2,3,̷ ...
ループによる全探索アルゴリズム
特定の条件を満たすようなものを発見する方法を探索アルゴリズムと言います。全探索は全ての場合を確認して、条件を満たすものが存在するかを判定します。
全探索アルゴリズムの中でもループを使ったものは基本とな ...
線形探索(Linear Search)
線形探索とは、入力を数値\(n\)とした時に、それがあるリストや配列に入っているかどうかを判定するためのアルゴリズムです。
1つのループ文を使うことでプログラムすることができます。
アルゴリズム\(i\) ...計算量同士の比較と入力サイズによる比較
計算量を見積もったところで、それの大きさが分からないと意味がありません。例えば、\(O(n^{100})\) と \(O(2^n)\) のどちらが大きいのでしょうか？
そこで、計算量同士の比較ができるように ...
最悪・最善・平均時のアルゴリズムの計算量の見積もり
「漸近記法」により数式の大体の大きさを見積もる方法を学びました。
しかし、アルゴリズムの計算量というものは、毎回常に同じ数式になるわけではありません。入力の大きさが同じであっても、形が違うだけで計 ...
漸近記法の定義とアルゴリズムの計算量の解析
プログラムを書く際は、読みやすく・保守が容易で・使いやすいものになるように注意しながら書く必要があります。なぜアルゴリズムの計算量を見積もる必要があるのでしょうか。
その答えは単純で ...