全探索 with 線形探索法
全探索 with 線形探索法
以下の３つの全探索問題を線形探索法を用いて解く方法を見ていく
- １つの配列から１つの要素を見つける O(N)
- ２つの配列から各々１つの要素を取り出し、最適な組み合わせを見つける O(N2)
- ある集合から最適な部分集合を見つける O(2N)
線形探索法とは (About Linear Search Method)
一つ一つの要素を順に調べていく
問題例
1. １つの配列から１つの要素を見つける
2. ２つの配列から各々１つの要素を取り出し、最適な組み合わせを見つける O(N2)
3. ある集合から最適な部分集合を見つける O(2N)
部分集合を2進数を使って表す方法
例: {a,b,c}の部分集合
| 添字 | 部分集合 | 2進数 |
|---|---|---|
| 0 | {} |
0b000 |
| 1 | {c} |
0b001 |
| 2 | {b} |
0b010 |
| 3 | {b,c} |
0b011 |
| 4 | {a} |
0b100 |
| 5 | {a,c} |
0b101 |
| 6 | {a,b} |
0b110 |
| 7 | {a,b,c} |
0b111 |
まとめ
全探索においては、「どうすればすべての場合を考慮し尽くせるか」ということが重要となる。
参考書籍
https://www.amazon.co.jp/問題解決力を鍛える！アルゴリズムとデータ構造-ＫＳ情報科学専門書-大槻兼資-ebook/dp/B08PV83L3N
