1

我在为这两个递归函数计算大 O 表示法时遇到了一些麻烦：

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

在上述情况下，我认为大 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

杜克林是正确的。第一个是 O(1)，第二个是 O(log N)

但是鉴于这个问题的标题，我认为重要的是要记住递归并不特殊。任何递归函数都可以重写为循环，与标准循环相比，它们没有区别。

于 2013-02-28T19:52:03.840 回答