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

Question

    int func(int n){
       if(n==1)
         return 0;
       else
         return sqrt(n);
    }

其中 sqrt(n) 是 C math.h 库函数。

1. O(1)
2. O(lgn)
3. O(lg lg n)
4. O(n)

我认为运行时间完全取决于 sqrt(n)。但是，我不知道这个功能实际上是如何实现的。

附言据我所知，求一个数的平方根的一般方法是使用牛顿法。如果我没记错的话，使用牛顿法的时间复杂度原来是 O(lg n)。那么答案应该是 O(lg n) 吗？

附言在我参加的最近一次测试中得到了这个问题。

Answer 1

我将给出一些更一般的案例答案，而不假设 int 的大小不变。

答案是Theta(logn)。

我们知道 newton-raphson 是 Theta(logn) - 不包括 Theta(n)(假设 sqrt() 尽可能高效)。

但是，一般数字 n 需要 log_2(n) 位进行编码 - 您需要读取所有的数字才能获得准确的 sqrt () 函数。这不包括 Theta(1) 和 Theta(log(log(n))。

从上面我们知道函数的复杂度是Theta(log(n))。

作为旁注，因为 O(log(n)) 是 O(n) 的子集 - 它也是一个有效的答案，虽然不是严格的.有关大 Theta 和大 O 及其差异的更多信息，您可能想查看 this thread .