クイックソート(QuickSort)
クイックソートは分割統治法を用いたソートアルゴリズムの一種です。安定ではない内部ソートとなっています。マージソートの様に、再帰関数を用いることで配列を2分割してソートします。
マージソートは分割した配列を ...
マージソート(Merge Sort)
マージソートは分割統治法を用いたソートアルゴリズムの1つです。配列を2分割することを繰り返し、小さい配列を一つ一つソートしてから「マージ(併合)」することで、最終的に高速にソートができます。
最終的に1つの ...
線形探索(Linear Search)
線形探索とは、入力を数値\(n\)とした時に、それがあるリストや配列に入っているかどうかを判定するためのアルゴリズムです。
1つのループ文を使うことでプログラムすることができます。
アルゴリズム\(i\) ...計算量同士の比較と入力サイズによる比較
計算量を見積もったところで、それの大きさが分からないと意味がありません。例えば、\(O(n^{100})\) と \(O(2^n)\) のどちらが大きいのでしょうか?
そこで、計算量同士の比較ができるように ...
最悪・最善・平均時のアルゴリズムの計算量の見積もり
「漸近記法」により数式の大体の大きさを見積もる方法を学びました。
しかし、アルゴリズムの計算量というものは、毎回常に同じ数式になるわけではありません。入力の大きさが同じであっても、形が違うだけで計 ...
漸近記法の定義とアルゴリズムの計算量の解析
プログラムを書く際は、読みやすく・保守が容易で・使いやすいものになるように注意しながら書く必要があります。なぜアルゴリズムの計算量を見積もる必要があるのでしょうか。
その答えは単純で ...
アルゴリズムの効率と時間計算量・領域計算量の定義
アルゴリズムの効率というのは、「計算量」と呼ばれる2つの指標によって評価することができます。
時間計算量 (time complexity)領域計算量 (space complexity)
...
イントロダクション: アルゴリズムとは何か
広い意味でいえば、アルゴリズムは「問題解決のための手順」のことです。料理のレシピなどもアルゴリズムといえるでしょう。
狭い意味での、つまり数学やコンピュータサイエンスの分