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.
9.3
凸包走査
■
289
1
なら、
p
は内部にあり削除できる。実装では、線分
s
が正確に極四辺形の頂点と交
差するような特別な場合も扱う。この計算は固定ステップなので、
O(1)
であり、全
点に対する
Akl-Toussaint
ヒューリスティックスは、
O(n)
となる。巨大なランダム
な点集合例では、初期の集合から半分近くの点を除くことができ、アルゴリズム全
体でコストのかかる整列化の処理が大幅に削減される。
9.3.4
分析
単位正方形からランダムに生成した
2
次元の点集合上で
100
回試行した。最良と
最悪の試行を棄却した残りの
98
試行の平均時性能結果を表 9-2に示す。この表は、
ヒューリスティックスを実行するときの平均時間の内容を示すだけでなく、なぜ
凸
包走査
が効率的なのか、背後にある理由を示している。
入力集合のサイズが増えると、
Akl-Toussaint
ヒューリスティックスでほぼ半数
の点を削除できる。驚くべきことに、凸包上の点の
個数は少ない。表9-2の第
2
列は、
凸包上の点の個数が
O(log n)
になるという主張を裏付けるものだ（
Preparata and
Shamos, 1985
）。当然ながら、分布が重要になる。単位円から一様に点を選べば、
凸包の点の個数は
n
の立方根のオーダーになる。
表9-2 実行時間（ミリ秒）と適用されたAkl-Toussaintのヒューリスティックス
N
凸包の点の
平均個数
計算
平均時間
Akl-Toussaint
により削除された
点の平均個数
Akl-Toussaintの
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.