algorithm - 大 O 符号和递归

Question

我在为这两个递归函数计算 Big 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 符号非常陌生，非常感谢任何帮助或解释!

Answer 1

对于calc :

此函数在递归期间永远不会被调用超过 5 次。从简短的分析中很容易看出并用几个值代替 n .因此它是 O(1) . 提示:n 越小，函数调用次数越多是(高于某个阈值)。

也许有点大胆的说法，但我相信任何函数(假设 n 是输入/输入大小)if (n > max) return const; 必须是O(1) (只需让“常数”成为 n <= max 所花费的最长时间)。

对于 method :

是的，是O(log n) .

该函数实际上是二分查找，这是一件好事。