以下のアルゴリズムの時間計算量はどれくらいですか？

以下のアルゴリズムの時間計算量を確認したいだけです。

編集：以下では、最適なデータ構造が使用されているとは想定していません。ただし、そのような構造を使用するソリューションを自由に提案してください（使用されるデータ構造と、それらが複雑さに与える有益な影響について明確に言及してください）。

表記法：以下では、n = | V |、m = | E |、およびavg_neighは、グラフ内の任意のノードの隣接ノードの平均数を示します。

仮定：グラフは重み付けされておらず、無向であり、隣接リスト表現がメモリにロードされています（各頂点の隣接リストを含むリストのリスト）。

これが私たちがこれまでに持っているものです：

1行目：次数の計算はO（n）です。これは、隣接リスト表現の各サブリストの長さを取得する、つまりn個のO（1）操作を実行するだけだからです。

3行目：最小値を見つけるには、すべての値、つまりO（n）をチェックする必要があります。これは、すべてのノードに1回アクセスするwhileループにネストされているため、O（n ^ 2）になります。

6〜7行目：隣接リスト表現からvの隣接リストがわかっているため、頂点vの削除はO（avg_neigh ^ 2）であり、隣接リストの各サブリストからvを削除するのはO（avg_neigh）です。6〜7行目はwhileループにネストされているため、O（n * avg_neigh ^ 2）になります。

9行目：1つのリストの長さを取得するだけなので、O（1）です。forループとwhileループにネストされているため、O（n * avg_neigh）になります。

要約：全体の複雑さはO（n）+ O（n ^ 2）+ O（n * avg_neigh ^ 2）+ O（n * avg_neigh）= O（n ^ 2）です。

注1：各サブリストの長さが利用できない場合（たとえば、隣接リストをメモリにロードできないため）、各リストには平均してavg_neigh要素が含まれているため、1行目の次数の計算はO（n * avg_neigh）です。 n個のサブリストです。そして9行目では、複雑さの合計はO（n * avg_neigh ^ 2）になります。

注2：グラフに重みが付けられている場合、隣接リスト表現にエッジの重みを格納できます。ただし、1行目の度数を取得するには、各サブリストを合計する必要があり、隣接リストがRAMにロードされている場合はO（n * avg_neigh）になり、それ以外の場合はO（n * avg_neigh ^ 2）になります。同様に、9行目はO（n * avg_neigh ^ 2）またはO（n * avg_neigh ^ 3）になります。