狠狠撸

箩补惫补によるアルゴリズム入门
2015/03/15/Kentsu141

アジェンダ
● プログラムとアルゴリズム
● プログラミングにおける
アルゴリズムとデータ構造の関係
● 时间计算量と性能の基準

プログラムとアルゴリズム

アルゴリズムとは：
処理を行う手順を記述したもの
例：
プログラム、料理レシピ、楽譜、数学の途中計
算...

つまりこういうこと？
アルゴリズム = プログラム（？）

そもそもなぜ
「データ構造」
が一緒に紹介されるか

プログラミングにおける
アルゴリズムとデータ構造の関
係

プログラミングにおけるアルゴリズムで考えるこ
とは
?メモリを使うが処理が早い
?メモリを使わないが処理が遅い
この２つが一般的に例として挙げられます
(時間と空間のトレードオフ)

特に、メモリ消費が多いが処理を速くするとき
この時の定石として
「はじめからある程度のデータを定義しておく」
という方法があります

そういった手段を使うとプログラムとしての
アルゴリズムが持つ計算量にデータ構造分を
「付け加えて考えないと行けない」

つまり
プログラム = アルゴリズム + データ構造

时间计算量と性能の基準

時間計算量とは
アルゴリズムの実行にかかる時間のこと
これをアルゴリズムの性能として扱うことが多い

計算量のうち
「最悪のケース」
つまり、一番時間がかかる時の計算量を
「最大計算量」といい
すべての人がかかる時間の平均の計算量を
「平均計算量」と言います

また入力されたデータをnとして
これに比例するアルゴリズムを
O(n)(nのオーダー)のアルゴリズムと言います
また、nを「領域計算量」と言います

計算方法は組むプログラムよって変わって来ます
ただ、現在確立されているアルゴリズムにおいて
は
時間計算量が判明しています

例えば、最速の「クイックソート」

クイックソートの
最大計算量はO(n^2)
平均計算量はO(n log n)
増加率に関してはまた今度

これがどれくらい速いか知りたいときは
「定本、javaプログラマのためのアルゴリズムとデータ
構造」という本を参考にしてみてください

まとめ
● プログラムとは
アルゴリズムとデータ構造を組み合わせたもの
● プログラミングでは
データ構造も含めてアルゴリズムを考える
● 时间计算量がアルゴリズムの优劣の基準になる

箩补惫补によるアルゴリズム入门