大O符号和递归

Question

我有一些麻烦，工作了大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），因为输入数据集是每次迭代减半？

但是，我对大O符号很陌生，任何帮助或解释都将不胜感激！

Answer 1

为calc：

此功能将永远不会递归过程中被调用的5倍以上。从简要分析中很容易看出，并用n代替了一些值。因此它是O(1)。 提示：函数将被调用更多次，更小的n（超过某个阈值）。

也许有点大胆的声明，但我相信任何功能（假设n是输入/输入尺寸）与if (n > max) return const;有是O(1)（只是让“常数”应采取的n <= max的最大时间）。

对于method：

是的，这是O(log n)。

该函数实际上是二进制搜索，这是一件很好的事情要知道。

Answer 2

Dukeling是正确的。第一个是O（1），第二个是O（log N）

但是，考虑到这个问题的标题，我认为重要的是要记住，递归并不是特别的。任何递归函数都可以重写为一个循环，与标准循环相比，它们看起来没什么区别。