グラフ内のノードの重みを計算するアルゴリズムの時間の複雑さは何ですか?
-
29-09-2020 - |
質問
グラフ上のすべてのノードの重みを計算するアルゴリズムの最良の時間の複雑さを見つけようとしています。ノードの重みは、それに隣接するエッジの重みの合計として定義されます。アルゴリズムは、すべてのノードの程度を計算し、確かにo(| V | + | e |)を算出するものと似ていると主張することができますが、私たちがの重みを計算しようとしているならば、私たちは同じことを言うことができます。ノード?
解決
for i in V:
weight(i) = 0
for e=(i,j) in E:
weight(i) = weight(i) + weight(e)
weight(j) = weight(j) + weight(e)
. 所属していません cs.stackexchange