質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

Q&A

1回答

771閲覧

トポロジカルソートの計算量がわかりません。

sss09

総合スコア0

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

0グッド

0クリップ

投稿2021/07/19 02:47

トポロジカルソート に関しての質問です。

BFSを利用したトポロジカルソート の計算量が頂点数n辺の数mのときO(m+n)というのはなぜでしょうか?
mがどこで出てくるのかがわからないです。
回答お願いします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

maisumakun

2021/07/19 02:54

質問が重複していますので、どちらかを削除依頼したほうがいいかと思います。
guest

回答1

0

O(n+m)って言うとわかりづらい(教科書に書いてあったんでしょうか?)ですが、ようはO(|V|+|E|)、つまりグラフの頂点(Vertex)と辺(Edge)の数です。
そしてこれはそのまんまbfsの計算量です。bfsは基本全ての頂点と辺を走査する必要があるのでその2つの合計が計算量になるんですね。
bfsのトポロジカルソートは最初に全頂点(|V|個)の辺数を数えた後にbfsしたりしてますが、V+(V+E)=2V+Eでも計算量では定数倍は無視するので結局O(|V|+|E|)です。

投稿2021/07/19 09:38

kairi003

総合スコア1330

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問