ノードを持つ DAG グラフを取得するアルゴリズムがあり、nノードごとに隣接ノードでバイナリ検索を実行します。私の知る限りでは、これはO(n log n)アルゴリズムですがn、ログの内部はノードの隣接関係にのみ対応するため、これはむしろO(n log m). これは、各ノードに隣接するノードmを意味しmます (これは直感的に、多くの場合、 よりもはるかに少なくなりますn)。
なぜO(n log m)ですか？は技術的に入力のサイズではないO(n log m)ため、意味がありません。さらに、ノードは他のすべてのノードに簡単に接続できるため、最悪のシナリオが発生する可能性があります。正しい？mnmn
ここには 2 つのケースがあります。
m、隣接するノードの数は定数によって制限されC、mn、隣接するノードの数は、ノードの数によってのみ制限されます最初のケースでは、は定数O(n)であるため、複雑さはです。Log(C)2 番目のケースでO(n*log(n))は、質問で説明した理由が原因です (つまり、 " mcan be n))。
Big O 表記はアルゴリズムの複雑さの上限を提供するため、m は最悪の場合 (正確には n - 1) で n に等しいため、正しい複雑さはO(n log n)になります。
There are certainly DAGs where one node is connected to every other node. Another example would be a DAG with nodes number 0,1,2...n, where every node has an edge leading to all higher numbered nodes.
There is precedent for giving a complexity estimate which depends on more than one parameter - http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm quotes a cost of O(|E| + |V| log(|V|). In some cases this might be useful information.
グラフの最悪のケースでは、各ノードに n-1 個の隣接ノードがあり、他のすべてのノードに接続されていることは正しいですが、すべてのノードがそうである場合、非巡回グラフにはなりません。したがって、各ノードの平均ネイバー数は n 未満です。
DAG 内のエッジの最大数: (n-1)n/2
各ノードを見ると、平均して (n-1)/2 個の隣接ノードがあります。したがって、最悪の場合でも、複雑さはO(n log n)のままです。