入門

クイックソートとは

クイックソートは分割統治法を用いたソートアルゴリズムの一種です。安定ではない内部ソートとなっています。マージソートの様に、再帰関数を用いることで配列を2分割してソートします。

マージソートは分割した配列を ...

マージソートとは

マージソートは分割統治法を用いたソートアルゴリズムの1つです。配列を2分割することを繰り返し、小さい配列を一つ一つソートしてから「マージ(併合)」することで、最終的に高速にソートができます。

最終的に1つの ...

線形探索とは

線形探索とは、入力を数値\(n\)とした時に、それがあるリストや配列に入っているかどうかを判定するためのアルゴリズムです。

1つのループ文を使うことでプログラムすることができます。

アルゴリズム\(i\) ...

計算量同士の比較

計算量を見積もったところで、それの大きさが分からないと意味がありません。例えば、\(O(n^{100})\) と \(O(2^n)\) のどちらが大きいのでしょうか？

そこで、計算量同士の比較ができるように ...

計算量は３つの場合を考える

「漸近記法」により数式の大体の大きさを見積もる方法を学びました。

しかし、アルゴリズムの計算量というものは、毎回常に同じ数式になるわけではありません。入力の大きさが同じであっても、形が違うだけで計 ...

なぜアルゴリズムを解析する必要があるのか

プログラムを書く際は、読みやすく・保守が容易で・使いやすいものになるように注意しながら書く必要があります。なぜアルゴリズムの計算量を見積もる必要があるのでしょうか。

その答えは単純で ...

アルゴリズムの効率

アルゴリズムの効率というのは、「計算量」と呼ばれる2つの指標によって評価することができます。

時間計算量 (time complexity)
領域計算量 (space complexity)

...

アルゴリズムの定義

広い意味でいえば、アルゴリズムは「問題解決のための手順」のことです。料理のレシピなどもアルゴリズムといえるでしょう。

狭い意味での、つまり数学やコンピュータサイエンスの分