はてなブックマーク

はじめに この記事は Qiita Engineer Festa 2022「アルゴリズム強化月間 - 楽しいアルゴリズムの世界を紹介しよう -」に向けて書いた記事です。 DFSとBFSの計算量は違うという話をしますが、この内容の日本語の記事は多分どこにもないと思うので、企画の賞選出基準の「記事のオリジナリティ」はあるかなと思います。 メインの部分は以下の2つの論文の結果となります。 A model classifying algorithms as inherently sequential with applications to graph searching Depth-first search is inherently sequential また、次の本も参考にしました。 Limits to Parallel Computation: P-Completeness Theory t