各親が無制限の数の子を持つことができるツリーであるデータ構造があり、ツリーの最大深さは 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) ですか?