int func(int n){
if(n==1)
return 0;
else
return sqrt(n);
}
Run Code Online (Sandbox Code Playgroud)
其中sqrt(n)是C math.h库函数.
我认为运行时间完全取决于sqrt(n).但是,我不知道这个功能是如何实际实现的.
PS找到我所知道的数字的平方根的一般方法是使用牛顿方法.如果我没有错,使用牛顿方法的时间复杂度变为O(lg n).答案应该是O(lg n)吗?
PPS在我最近出现的测试中得到了这个问题.
这取决于实现sqrt以及您感兴趣的时间复杂度。
我想说你可以认为它是“常数”,所以 O(1),从这个意义上说:如果你输入一个 random int,它平均会花费相同的时间。(原因:多位数字更为常见)。
但看看这里。另一个可能的答案是 O(M(n)),其中 M(n) 是乘法的复杂度,n 是整数中的位数。
这看起来像是教科书上的问题,而且可能是一个陷阱。老师可能想检查您是否能够区分计算sqrt数字列表(这将是 O(n))和单个数字(这将是 O(1))。
请注意,“正确”答案通常还取决于提问的上下文。
我将给出一些更一般的案例答案,而不假设大小不变int.
答案是Theta(logn).
我们知道newton-raphson是Theta(logn) - 排除Theta(n)(假设sqrt()尽可能高效).
但是,一般的数字nrequries log_2(n)位编码-你需要阅读这一切,为了得到准确的sqrt()功能.这不包括Theta(1)和Theta(log(log(n)).
从上面我们知道函数的复杂性Theta(log(n)).
作为旁注,因为它O(log(n))是一个子集O(n)- 它也是一个有效的答案,虽然不是很紧的.有关big Theta和big O及其差异的更多信息,您可能需要查看此主题.
| 归档时间: |
|
| 查看次数: |
7235 次 |
| 最近记录: |