宿題問題については、グラフが隣接リストによって表されるn個のノードとm個のエッジの集合、なぜinsertVertexがO（1）をとり、deleteVertexがO （m）。時間複雑度/グラフ理論
私は私の答えを完全にはわかりませんが、insertVertexはO（1）です。最初に挿入すると、配列に追加するのはすべて1つのノードと隣接する頂点のセット新しいノードがポイントする）。したがって、この時間の複雑さは一定である。ただし、ノードを削除するときには、ノードとそのノードに付随する隣接するエッジを削除する必要があるだけでなく、残りのmエッジを通過して、それらを削除する必要がありますあなたが削除しようとしているノード（何も指さないエッジを持てないので）
私はグラフ理論には新しいので、自分の考え方が正しいかどうかわかりません。素晴らしいこと。
おかげ
O（m）の説明は正しいです。
リンクリストの操作に関して説明した方がよいでしょう。リンクされたリストにノードを追加するのにO（1）時間かかる。そして、アイテムを削除するのにO（n）時間がかかります。
a）なぜinsertVertexがO（1）であるのですか？
頂点を挿入するのは、リンクされたリスト（O（1））にノードを追加することだけで、グラフが無向であれば2になります。
b）deleteVertexがO（m）である理由
頂点を削除すると、意味：
1）を使用すると、すべてのリンクされたリストから頂点を削除する必要があります最悪の場合、リンクされたリスト（O（1））
2）を削除しますO（ m）。それはO（m）なので、すべてのリンクリストのノード数はm、グラフが無向であれば2 * mです。
insertVertexはO（1）あなただけのデータ構造の最後に新しい要素を追加するためとる。
deleteVertexは、すべてのエッジに対して、エッジが指し示しているか、指し示しているか（Gが指示されているかどうか）を頂点からチェックする必要があるため、O（m）をとります。
あなたの意見を読んでいるようですが、OPを読んでください。
私には堅実な推論のように聞こえますが、他の人がここでさらに明確にすることができるでしょう。 –