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.
188
■
6
章 グラフアルゴリズム
6.8.3
分析
プリム法
の初期化では、（二分ヒープで実装された）優先度付きキューに全節点を
挿入するので、全コストが
O(V log V)
となる。
プリム法
の
decreaseKey
は、キュー
の要素数を
q
（これは
|V|
より常に小さい）とすると
O(log q)
の性能となる。どの節
点も優先度キューから
1
度だけ取り出され、どの無向辺も正確に
2
度ずつ訪問され
ることから、この演算は高々
2*|E|
回呼ばれることがわかる。したがって、全体性
能は、
O((V
＋
2*E)*log n)
、すなわち
O((V
＋
E)*log V)
となる。
6.8.4
変形
プリム法
の代わりになるものとして、
クラスカル法
（
Kruskal's Algorithm
）がある。
クラスカル法
は、「素集合」データ構造を用いて、最小被覆木を構築する。
クラスカ
ル法
はグラフのすべての辺をその重み順に処理する。すなわち、最小重みの辺から
始め、最大重みの辺で終える。
クラスカル法
は、
O(E log E)
で実装できる。素集合
データ構造に工夫を凝らした実装だと、これが
O(E log V)
になる。
クラスカル法
に
ついての詳細は（
Cormen et al., 2009
）に書かれている。
6.9
グラフについての考察
本章では、グラフが疎か密かでアルゴリズムの振る舞いが異なることを示した。
この概念をさらに検討して、疎グラフと密グラフとの間の性能分岐点を分析し、ス
トレージ要求への影響を理解する。
6.9.1
ストレージの問題
集合の
n
個の要素間の ...
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.