2019年11月24日ソート入門,ソート,クイックソート

クイックソートとは

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

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

2019年11月24日ソート入門,ソート,マージソート,分割統治法

マージソートとは

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

最終的に1つの ...

2019年11月21日探索入門

線形探索とは

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

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

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

2019年11月20日アルゴリズム概要入門

計算量同士の比較

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

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

2019年11月20日アルゴリズム概要入門

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

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

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

2019年11月20日アルゴリズム概要入門

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

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

その答えは単純で ...

2019年11月20日アルゴリズム概要入門

アルゴリズムの効率

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

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

...

2019年11月19日アルゴリズム概要入門

アルゴリズムの定義

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

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