25

一般的なグラフでの BFS と DFS の実行時間は O(n+m) であることがわかりました。ここで、n はノードの数、m はエッジの数です。これは、ノードごとに隣接リストを考慮する必要があるためです。しかし、BFS と DFS をバイナリ ツリーで実行した場合の実行時間はどのくらいですか? ノードから出ることができるエッジの可能な数は一定 (つまり 2) であるため、O(n) であるべきだと思います。この認識が正しいか確認してください。そうでない場合は、バイナリ ツリーでの BFS と DFS の正しい時間計算量を説明してください。

4

2 に答える 2

24

BFSとDFSの時間計算量は、O(|E|)またはあなたの場合はO(m)です。

二分木でmは は に等しいn-1ので、時間計算量は に等しくなりO(|V|)ます。m頂点ごとの隣接するエッジの平均数ではなく、エッジの総数を指します。

于 2013-11-11T08:21:14.617 に答える
22

はい、O(n) は正しいです。

また、エッジの数は、ノードの数 - 1 としてより正確に表すことができることに注意してください。これは、ルートを除く各ノードに親からそれ自体へのエッジがあり、これらのエッジがすべてをカバーしていることを考慮すると、非常に簡単に確認できます。ツリーに存在するエッジ。

于 2013-11-11T08:23:16.720 に答える