2

したがって、このアルゴリズムを実装し、その時間の複雑さを分析した後、その上限が O(n^2*m) によって制限されていることがわかりました。ここで、n はグラフ内の頂点の数で、m はエッジの数です。これが3次アルゴリズムと見なされるかどうか疑問に思っていますか? O(n^3) が立方体であることは知っていますが、「m」のためにわかりません。それが立方体であるか、他のタイプの複雑さであるかを説明できる人はいますか?

4

1 に答える 1

3

グラフ アルゴリズムは、時間の複雑さに関する特殊なケースを提示します。技術的には、m = O(n^2) であるため、O(n^2*m) は4 次(O(n^4)) です。ただし、多くのグラフ アルゴリズムはエッジの数に敏感であるため、その感度を反映するために、複雑さを頂点とエッジの関数として個別に報告します。グラフが疎 (m = O(n)) の場合、O(n^2m) は 3 次ですが、より密なグラフでは、4 次アルゴリズムのように動作します。

于 2014-10-10T18:27:02.323 に答える