webdevqa.jp.net

バイナリツリー上のBFSとDFSのランタイムはO(N)ですか?

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

13
gmemon

[〜#〜] bfs [〜#〜] および [〜#〜] dfs [〜#〜] の時間計算量はO(|E|)です、またはあなたの場合、O(m)

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

16
kevmo314

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

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

11
Dukeling