1

これらの 2 つの再帰関数の Big O 表記法を作成するのに問題があります。

int calc (int n) 
{
  if (n <= 0)
    return 0 ;
  else if (n > 10) 
    return n ;
  else
    return calc (5 + calc(5n));
}

上記の場合、データセットのネストされた反復のために、Big O 表記は O(n^2) である可能性があると思いますか?

boolean method (int k ,int [] arr, int i, int j)
{
    if (i > j)
       return false;
    if (arr [(i+j)/2] == k)
       return true;
    if (arr [(i+j)/2] < k)
       return method (k, arr, i, ( (i+j)/2) - 1) ;
    else
       return method (k, arr, ((i+j)/2)+1, j) ;
}

ここで、入力データセットは反復ごとに半分になるため、大きな O 表記は O(log N) になる可能性があると思いますか?

しかし、私は Big O 記法に非常に慣れていないので、助けや説明をいただければ幸いです。

4

2 に答える 2

3

の場合calc:

この関数は、再帰中に 5 回以上呼び出されることはありません。簡単な分析と のいくつかの値の代入から簡単に確認できますn。したがって、それはO(1)です。ヒント: 関数は小さいほど多くの回数呼び出されますn(しきい値を超える)。

少し大胆な発言かもしれませんnが、(入力/入力サイズであると仮定しif (n > max) return const; て)どの関数もそうである必要があると思いますO(1)(「定数」を にかかる最大時間としますn <= max)。

の場合method:

はい、O(log n)です。

関数は実際には二分探索であり、これは知っておくとよいことです。

于 2013-02-28T19:31:13.697 に答える
0

デューケリングは正しいです。1 つ目は O(1) で、2 つ目は O(log N) です。

しかし、この質問のタイトルを考えると、再帰は特別ではないことを覚えておくことが重要だと思います。再帰関数はすべてループとして書き直すことができ、標準のループと比較して違いはありません。

于 2013-02-28T19:52:03.840 に答える