アルゴリズムとデータ構造

アルゴリズムとデータ構造

もくじ
1. どうしてアルゴリズムを学ぶのか
2.

オーダーとは？

3.

使用例

4.

ソート

5.

クイックソートについて詳しくみていく

6.

演習どうしてアルゴリズムを学ぶのか？

「ぶっちゃけ、標準ライブラリに良い感じに揃ってるし、知らなくて良くない？」

「ぶっちゃけ、標準ライブラリに良い感じに揃ってるし、知らなくて良くない？」

まあ、確かに...

「ぶっちゃけ、標準ライブラリに良い感じに揃ってるし、知らなくて良くない？」

まあ、確かに...

わたしが考える答え
1. どのようなアルゴリズムが存在し、どんな場面で使えるかのインデックスを貼っておける
2. 内容を知ることで、より適切に使い分けることができる
3. 複雑な処理を独自実装しなければならないいざという時に役に立つ（マッチング、おすすめ編成、Lvアップの消費アイテム自動選択 etc…）

オーダーとは？

オーダーとは？
・アルゴリズムの計算量を表す概念
・計算量は大きく二つに分けられる。
時間計算量（処理時間の計算量）
空間計算量（メモリ使用量の計算量）

・単に計算量（オーダー）と言った場合、時間計算量のことを指す。
・Big O 記法を用いて表す
例: O(log(n))

オーダーの書き方
・データの長さ（量）を n として、その処理に本来かかる処理の式の 次数が一番高い項のみに着目する。係数は無視する
例えば、なら、になる。

・O(1) … 処理ステップ数は n に関わらず常に一定
・O(n) … 処理ステップ数は n に比例・O(n^2) … 処理ステップ数は n^2 に比例オーダーの比較
・n が小さいとほとんど差はない
・そもそも n が小さい場合は処理に負担がかからないのであんまり関係ない・n が限りなく大きい時を考える→ 最大次数の項以外は無視できるオーダーの比較
・n! など、オーダーがあまりにも大きい場合は現実的に使えない・あまりに大きいオーダーになる場合はアルゴリズムが適切でない場合もあるので見直した方が良さそうオーダーの例

配列arr の要素数を n とする

オーダーの例
O(n)・for が2回繰り返されている→ 2n になる・ただし係数は無視するため、O(n) となる

配列arr の要素数を n とする

オーダーの例

配列arr の要素数を n とする

2

オーダーの例

配列arr の要素数を n とする

O(n^2)
・for が2つ入れ子になっている。arr1の要素1つにつき arr2 の要素全てを参照するので、n * n → O(n^2)
2オーダーの例

配列arr の要素数を n とする

オーダーの例
O(1)・arr の要素数に関係なく必ず一定の値を返す → O(1)配列arr の要素数を n とする

オーダーの例

配列arr の要素数を n とする

ヒント: 1回のループで検索対象が半分ずつに狭まっていき、最終的に目的のものを検索するアルゴリズム

オーダーの例
O(log(n))
・arr の要素数が 8 だとすると、8 → (処理) → 4 → (処理) → 2 →(処理) → 1 と半分ずつに候補が減っていく。結果、3回の処理で検索が完了するので、O(log(n))

配列arr の要素数を n とする

使用例

使用例
使用すると経験値がもらえるアイテムを適切に配布する処理
アイテム小 → 経験値800
アイテム中 → 経験値2000
アイテム大 → 経験値3000

経験値 5500をアイテムに変換したい！
1.

2.

配布するアイテムは経験値の合計が実際に付与するはずだった経験値以上で、かつ存在しうるアイテムの組み合わせの中で最小になるようにする
配布するアイテムの個数はなるべく少なくなるようにする1.

アイテムの種類を、もらえる経験値の降順にソートする（アイテム大が最初）

2.

その種類のアイテムについて、配布したい経験値量を「ギリギリ超える個数」と「ギリギリ超えない個数」の2パターンを計算し、配列に入れる

使用例
使用すると経験値がもらえるアイテムを適切に配布する処理
アイテム小 → 経験値800
アイテム中 → 経験値2000
アイテム大 → 経験値3000

経験値 5500をアイテムに変換したい！
1.

2.

配布するアイテムは経験値の合計が実際に付与するはずだった経験値以上で、かつ存在しうるアイテムの組み合わせの中で最小になるようにする
配布するアイテムの個数はなるべく少なくなるようにする

経験値5500の場合、アイテム大 2個（ギリギリ超える） → 6000
アイテム大 1個（ギリギリ超えない） → 3000

3.

配列に入っているパターンそれぞれの残り必要な経験値をもとに、手順 2の次の種類について再度計算する

使用例
大×2

合計経験値 : 6000

大×1

合計経験値 : 3000

使用例
中
大×0

合計経験値 : 6000

×2

中×0

合計経験値 : 6000
合計経験値 : 6000

中
大×2×1

合計経験値 : 3000

合計経験値 : 7000

中×1

合計経験値 : 5000

小×0

合計経験値 : 6000

使用例

小×0

合計経験値 : 6000

中
大×0

合計経験値 : 6000

小×0

合計経験値 : 6000

×2

中×0

小×0

合計経験値 : 6000

合計経験値 : 6000
合計経験値 : 6000

小中
大×2×0

合計経験値 : 7000

×1

合計経験値 : 3000

合計経験値 : 7000

小中合計経験値 : 7000

×1

合計経験値 : 5000

小×0×1

合計経験値 : 5800

小×0

合計経験値 : 5000

小×0

合計経験値 : 6000

使用例

小×0

合計経験値 : 6000

中
大×0

合計経験値 : 6000

小×0

合計経験値 : 6000

×2

中×0

小×0

合計経験値 : 6000

合計経験値 : 6000
合計経験値 : 6000

小中
大×2×0

合計経験値 : 7000

×1

合計経験値 : 3000

合計経験値 : 7000

小中合計経験値 : 7000

×1

合計経験値 : 5000

小×0

×1

合計経験値: 5800

小×0

合計経験値 : 5000

1.

アイテムの種類を、もらえる経験値の降順にソートする（アイテム大が最初）

2.

その種類のアイテムについて、配布したい経験値
量を「ギリギリ超える個数」と「ギリギリ超えない個数」の2パターンを計算し、配列に入れる

使用例
使用すると経験値がもらえるアイテムを適切に配布する処理
アイテム小 → 経験値800
アイテム中 → 経験値2000
アイテム大 → 経験値3000

経験値 5500をアイテムに変換したい！
1.

2.

配布するアイテムは経験値の合計が実際に付与するはずだった経験値以上で、かつ存在しうるアイテムの組み合わせの中で最小になるようにする
配布するアイテムの個数はなるべく少なくなるようにする

経験値5500の場合、アイテム大 2個（ギリギリ超える） → 6000
アイテム大 1個（ギリギリ超えない） → 3000

3.

配列に入っているパターンそれぞれの残り必要な経験値をもとに、手順 2の次の種類について再度計算する→→→

使用例の計算時間n = 1000 のとき

O(n) →O(n^2) →O(2^n) →MacBook Air (13-inch, Early 2015)
プロセッサ: 1.6GHz Intel Core i5使用例の計算時間n = 1000 のとき

O(n) →0.000003秒

O(n^2) →O(2^n) →MacBook Air (13-inch, Early 2015)
プロセッサ: 1.6GHz Intel Core i5使用例の計算時間n = 1000 のとき

O(n) →0.000003秒

O(n^2) → 0.003秒

O(2^n) →MacBook Air (13-inch, Early 2015)
プロセッサ: 1.6GHz Intel Core i5使用例の計算時間n = 1000 のとき

O(n) →0.000003秒

O(n^2) → 0.003秒

O(2^n) → 10^284年 → 1垓無量大数無量大数無量大数 年
MacBook Air (13-inch, Early 2015)
プロセッサ: 1.6GHz Intel Core i5使用例の計算時間

今回の使用例では n=3 なので、実際に使えるという判断になる
ただし、仕様変更で n>=4 になるかもしれない事は想定し、プランナーさんと相談するなどして慎重に決める

ソート

ソートアルゴリズム
・データを一定の順序に並べ替えるソートは色々な手法があり、アルゴリズムの研究がされてきた・アルゴリズムの説明をする際にもしばしば用いられる

代表的なソート
・選択ソート - O(n^2)
わかりやすい。が、最初に思いつくアルゴリズ
ムだけに、遅い。
1.
2.
3.

データの中で最も小さい値を探して先頭にもってくる。
残ったデータの中で最も小さい値を二番目にもってくる。
これを繰り返す。

代表的なソート・バブルソート - O(n^2)
わかりやすい。泡のように浮き上がっていくのが由来。遅い。
1.
2.

先頭から順番に隣り合った要素を比較し、順番が逆であれば入れ替える。
これを n-1 回繰り返す。

代表的なソート・マージソート - O(n log n)
ちょっとむずい。クイックソートよりは平均的に遅いが、並び順が安定している。
1.
2.

要素を2分割していき、要素数が分割数1になるまで繰り返す。
これを逆順に辿っていき、それぞれのステップで小さい順（大きい順）に並べつつ合体（マージ）して元に戻していく代表的なソート・ヒープソート - O(n log n)
むずい。早い上に、空間計算量に優れていて余計なメモリを使わないのが特徴。
1. TODO代表的なソート・クイックソート - O(n log n)
早い上に、空間計算量に優れていて余計なメモリを使わないのが特徴。
1. 適当な値（pivot）を選択する
2. pivot未満の要素を配列の先頭側（左側）に集め、pivotより大きい要素は後側（右側）に集める
3. 分割されたそれぞれの区間に対し、再びpivotの選択と分割を行う
4. これ以上分割できなくなったら終了よくあるソートの比較
性質

選択ソート

バブルソートマージソートヒープソート

クイックソート

安定か安定

安定

安定

不安定

不安定

最悪計算量

O(n^2)

O(n^2)

O(n log n)O(n log n)O(n^2)

最良計算量

Ω(n^2)

Ω(n)Ω(n log n)Ω(n log n)Ω(n log n)

平均計算量

Θ(n^2)

Θ(n^2)

Θ(n log n)Θ(n log n)Θ(n log n)よくあるソートの比較
性質

選択ソート

バブルソートマージソート

クイックソート

安定か安定

安定

安定

不安定

最悪計算量

O(n^2)

O(n^2)

O(n log n)O(n^2)

最良計算量

Ω(n^2)

Ω(n)Ω(n log n)Ω(n log n)

平均計算量

Θ(n^2)

Θ(n^2)

Θ(n log n)Θ(n log n)【Unity】ソートアルゴリズム12種を可視化してみた - Qiita

クイックソートについて詳しくみていくクイックソート - O(n log n)9-35268-613

クイックソート - O(n log n)(pivot はとりあえず分割された配列の中の一番後ろの要素にする）

pivot
9-3

5268-613

クイックソート - O(n log n)

9-3

52

63

8-6

1

クイックソート - O(n log n)pivot より小さい-3

2-6

pivot より大きい
1

3

9568

クイックソート - O(n log n)

-3

2-6

1

3

9568

クイックソート - O(n log n)(pivot はとりあえず分割された配列の中の一番後ろの要素にする）

pivot-32-6

1

pivot
39568

クイックソート - O(n log n)

-3

2

1-6

3

9568

クイックソート - O(n log n)3
pivot より小さい-3-6

pivot より大きい
12pivot より小さい
56

pivot より大きい
89クイックソート - O(n log n)
3-3-6

1

2

5689

クイックソート - O(n log n)(pivot はとりあえず分割された配列の中の一番後ろの要素にする）

3
pivot
-3-6

pivot
1

2

5689

クイックソート - O(n log n)
3-3-6

1

2

58

69

クイックソート - O(n log n)
3

1
pivot より大きい
-6-3

2

8
pivot より小さい
569

クイックソート - O(n log n)

-6-3

12

3

5完成！！

689

クイックソートの手順とオーダー1.

配列の中から pivot を1つ選ぶ→ O(1)

2.

配列の要素を1つずつ全部みて、pivot より小さければ左側、大きければ右側に集める→ O(n)

3.

分割されたそれぞれの配列について、再帰的にクイックソートする（1に戻る）→ O(log(n))

1 * n * log(n) → O(n log(n))

クイックソートの手順とオーダー
1.

配列の中から pivot を1つ選ぶ→ O(1)

2.

配列の要素を1つずつ全部みて、pivot より小さければ左側、大きければ右側に集める→ O(n)

3.

分割されたそれぞれの配列について、再帰的にクイックソートする（1に戻る）→ O(log(n))
ちなみに ...

log(n)の部分（小さく分割していき、再度その配列について同じことを考える）は、早いアルゴリズムによく使われる考え方↓分割統治法演習

演習
・クイックソートを、自分の好きな言語で実装してみよう演習・pivot の選択を工夫してみよう演習・pivot の選択を工夫してみよう
回答例: 先頭・中間・末尾 の3つのデータの中央値を返す

次回

データ構造編に続く...