complexity-theory - 指標関数の繰り返し

Question

次のような再帰関数があるとします。

最初の if ステートメントの再帰関係は O(n) になり、else 条件の再帰関係は O(logn) になることがわかっています。ただし、関数全体の複雑さを計算するのは混乱しています。nがlog（n）を支配するため、全体的な複雑さは単純にO（n）になりますか？

Answer 1

定義により、大きな O は上限なので、O(n) になります (O(n) は O(lg(n)) より大きいため) 大きな O と大きなシータについて少し読んでください Big-oh vs big-シータ

編集：

コードが次のようになると仮定します。

foo(x,y)
{
 if(y<0):
  //call some other function, or throw an error, otherwise we're stuck in an infinite loop
 else if(y==0):
   return 1
 else if(y%2!=0):
   return x*foo(x,y-1)
 else:
   return foo(x,y/2)*foo(x,y/2)
}

ここで、Big O は O(n) ですが、技術的に言えば、O(n^2)、O(n^3) などになります。これは、Big O が上限であるためです。

Big Theta (タイト バウンド) は Theta(n) です。

y/2 を除算して y を減らすことができるからといって、foo の呼び出しを減らすわけではないことに注意してください。関数呼び出しを 2 倍にするため、Theta(lg(n)) のパフォーマンスは得られません。

Answer 2

O(n) が最悪のケースで、O(logn) が最良のケースに分解できると思います。

いくつかのアイデアを与えるだけで、これは完全な答えではありません。