December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
3.6
一般的なアプローチ
■
49
3.6
一般的なアプローチ
本書で使われる基本的なアルゴリズムのアプローチを本節で示す。これらの一般
的な問題解決戦略を理解して、具体的な問題で解決に向けてどのように適用すれば
よいか把握する必要がある。
10
章には、正確でなくても許容可能な近似解やしらみ
つぶし探索の代わりに適切な結果に収束する大量試行による乱択方式など他の戦略
を追加してある。
3.6.1
貪欲法
貪欲法（
Greedy
）は、サイズ
n
の課題をステップを踏んで順次問題を解くことに
よって完遂する。各ステップで、貪欲アルゴリズムは、利用可能な情報から最良の
局所決定を行い、通常は解く問題のサイズを
1
つ減らす。
n
ステップ完了すれば、
アルゴリズムは計算した解を返す。
例えば、
n
個の数の配列
A
を整列するのに、貪欲選択ソートアルゴリズムは、
A[ 0, n
−
1]
の最大値を見つけて
A[n
−
1]
の要素と入れ替える。これで、
A[n
−
1]
は適切な位置に収まった。次のプロセスでは、残りの
A[ 0, n
−
2]
の最大値を見つ
けて
A[n
−
2]
の要素と入れ替える。このプロセスが配列全体を整列するまで続く。
詳細は
4
章を参照。
貪欲戦略は、アルゴリズムが入力を処理するにつれて、解かれる部分問題が徐々
に狭くなると特徴付けることもできる。部分問題が
O(log n)
で完了するなら、貪欲
戦略は
O(n log n)
性能を示す。選択ソートのように、部分問題が
O(n)
の振る舞い
なら、全体性能は
O(n
2
)
となる。
3.6.2
分割統治
分割統治
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.