1

各親が無制限の数の子を持つことができるツリーであるデータ構造があり、ツリーの最大深さは 4 です。各レベルは異なるクラスです。

私の友人は、これをトラバースするアルゴリズムを作成しました。これは for ループで構成されており、疑似コードは以下のとおりです。

root = tree.root();
for (int i = 0; i < root.children_size(); i++)
    child1 = root.child(i);
    for(int j = 0; j < child1.children_size(); j++)
        child2 = child1.child(j);
        for(int k = 0; k < child2.children_size(); k++)
            child3 = child2.child(k);

彼は、これには 3 つの for ループがあるため、このアルゴリズムの実行時間は O(n3) であると主張しています。n とは何かと尋ねると、彼は for ループの数だと言いましたが、これは意味がありません。なぜなら、n はこのツリー内の構造でなければならないからです。実行時間は O(root.children_size + child1.children_size + child2.children_size) になるため、n はツリー内のノード全体の数であり、このアルゴリズムの実行時間は O(n) であると主張します。

実行時間についての私の仮定は正しいですか、O(n)、それとも私の友人は O(n^3) ですか?

4

2 に答える 2

1

はい、あなたは正しいです。あなたは実際に深さ優先検索を採用しています。これは各ノードを正確に 1 回 (つまり、dfs の最悪の場合) 訪問するため、複雑さは O(N) です。 (つまり、for ループの数) ここは固定です。

于 2012-11-08T06:45:33.673 に答える
0

あなたが正しいです。すべてのノードを 1 回訪問すると、O(N) になります。ここで、N は総数です。ツリー内のノードの数。

于 2012-11-08T06:34:57.820 に答える