競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
122: (ﾜｯﾁｮｲ 7f55-EYsv) 2023/04/06(木)17:29 ID:AU30dZob0(1/2) AAS
幅優先探索の計算量が O(N + M)（N は頂点数, M は辺数）ですが、
N と M は異なる種類の変数です。
計算量は、 O(N + M) ですと言われてもピンときません。
普通は、 N << M だと思うので、 O(M) でいいような気がします。
例えば、連結グラフの場合、 N - 1 ≦ M ですよね。
126: (ﾜｯﾁｮｲ 7f55-EYsv) 2023/04/06(木)17:51 ID:AU30dZob0(2/2) AAS
O(N + M) ですと教えてもらって何が嬉しいですか？
この情報をどう利用しますか？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.018s