我在为这两个递归函数计算 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 符号非常陌生,非常感谢任何帮助或解释!
最佳答案
对于calc
:
此函数在递归期间永远不会被调用超过 5 次。从简短的分析中很容易看出并用几个值代替 n
.因此它是 O(1)
. 提示:n
越小,函数调用次数越多是(高于某个阈值)。
也许有点大胆的说法,但我相信任何函数(假设 n
是输入/输入大小)if (n > max) return const;
必须是O(1)
(只需让“常数”成为 n <= max
所花费的最长时间)。
对于 method
:
是的,是O(log n)
.
该函数实际上是二分查找,这是一件好事。
关于algorithm - 大 O 符号和递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15143167/