0
私はマルチグラフとして表現できる問題があります。このグラフを内部的に表現するために、私は行列を考えています。私は頂点の辺の数を数えたいので、行列の考え方が好きです。これはO（n）時間になります。なぜなら、正しい列をループするだけで時間の複雑さがグラフの頂点の量に線形になるからです。しかし、私はまた、空間の複雑さを考えています。このグラフが大きくなると、無駄なスペースが多くなります。これは私に隣接リストを使用することにつながります。これは私の空間の複雑さを減らすかもしれませんが、私の時間の複雑さのように聞こえるだけで、特定の頂点の辺の数を決定したい場合、どのように時間の複雑さを表現するのですか？私はこの操作が最初に頂点を見つけてこの操作がO（n）になるようにすることを知っていますが、O（n）でも可能な辺のリストをスキャンする必要があります。これは、この操作の時間の複雑さがO（n^2）であることを意味しますか？マルチグラフと隣接リスト
編集：私はハッシュテーブルを使用した場合、最初の操作はOだろうと思い
（1）そのためには、頂点のための辺の数を見つけるために私の操作を意味しているのは、O（n）はありますか？
申し訳ありません私は| e | << | v | ** 2 –
私はちょっと混乱しています。だから、もし私がハッシュテーブルを持っていて、それぞれのハッシュが隣人の配列を持っていたら、最悪で配列を横切らないのはO（n）ですか？ –
はい、あなたはnが端数であるとは言わないので混乱します。ノードの数をnとすると仮定しますが、意味はありません。ごめんなさい。 –