c++ - BigOとツリートラバーサル

Question

私がこのような機能を持っていた場合：

void myfunction(node* root)
{
   for(int i = 0; i<root->children.size();i++)
   {
      myfunction(root->children[i]);
   }
}

それはn^2のBigOですか、それともnのBig Oですか？forループがあり、そのforループ内にそれ自体への関数呼び出しがある場合、Big Oは反復回数に関数を掛けたものですか？

Answer 1

これは n ツリーの順序どおりのトラバーサルですが、すべての要素にヒットするため、O(n) になります (big-theta の方が適切です)。

Answer 2

再帰的な関数呼び出しです。Big O表記で時間計算量を計算するには、再帰関係を少し調べる必要があります。あなたの推論は、一般的なケースでは正しいです。この特定のケースでは、回答は既に投稿されています。

編集:再帰関数の Big-Oh の説明については、このリンクを参照してください。

Answer 3

これは、N 個のノードを持つツリーに何が起こるかを考えることで解決できます。

この関数は、ツリー内のすべてのノードに対して 1 回呼び出されるため、O(N) と Big-Theta(N) の両方が呼び出されます。

O 値が大きい場合、ツリーの幅とツリーの高さは関係ありませんが、訪問回数は同じです。

つまり、深さと幅は、関数のスペースに関する考慮事項に影響を与えます。

ツリーの幅が非常に広い場合 (たとえば、任意の N に対して深さが常に一定になるように幅が設定されている場合)、トラバーサルに必要なスタック スペースは一定です。
ただし、幅が固定定数値 > 1 の場合、必要なスタック領域は O(log(N)) です。
幅が 1 の縮退した場合、ツリーは連結リストになり、必要なスペースは O(N) になります。
一部の言語/コンパイラは、再帰を最適化してスペース要件が実際に一定になるようにすることができます（ただし、これは、トラバーサル中に何を行っているか/戻っているかによって異なります）。

Answer 4

数学、コンピュータ サイエンス、および関連分野では、引数が特定の値または無限大に向かう傾向がある場合、通常はより単純な関数の観点から、ビッグ O 記法は関数の制限動作を表します。Big O 記法を使用すると、ユーザーは成長率に集中するために関数を単純化できます。同じ成長率を持つさまざまな関数を同じ O 記法を使用して表すことができます。

残りはこちら。
そして、あなたの例に関しては、間違いなく O(n) があります。

Answer 5

これは O(n) です。ここで、n はツリー内のノードの総数です。