以下函数的时间复杂度是多少？

  • Z时代
  • 2024-01-10
  • 分类：问答

int func(int n){

if(n==1)

return 0;

else

return sqrt(n);

}

其中sqrt（n）是C math.h库函数。

  1. O（1）

  2. O（lg n）

  3. O（lg lg n）

  4. 上）

我认为运行时间完全取决于sqrt（n）。但是，我不知道该功能是如何实现的。

PS找到我知道的数字的平方根的一般方法是使用牛顿法。如果我没看错，那么使用牛顿法的时间复杂度就是O（lg n）。那么答案应该是O（lg n）吗？

PPS在我出现的最新测试中遇到了这个问题。

回答：

我将给出更一般的案例答案，而不假设的大小恒定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)因此尽管不是很严格的答案，但这也是有效的答案。有关大Theta和大O及其差异的更多信息

以上是 以下函数的时间复杂度是多少？ 的全部内容， 来源链接： utcz.com/qa/405861.html

回到顶部