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

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

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

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

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

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

我将给出一些更一般的案例答案，而不假设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)的子集 – 它也是一个有效的答案，尽管不是紧的答案。有关big Theta和big O及其差异的更多信息，您可能希望查看此主题。

这取决于sqrt的实现以及您感兴趣的时间复杂度。

我会说你可以认为它是“常数”，所以O（1），在这个意义上：如果你输入一个随机的int ，它将平均花费相同的时间。（原因：有很多位数的数字更常见）。

但看看这里。另一个可能的答案是O（M（n）），其中M（n）是乘法的复杂度，n是整数中的位数。

这看起来像一个教科书问题和一个也许意味着陷阱。老师或许想要检查你是否可以区分计算sqrt的数字列表（可能是O（n））和单个数字（可能是O（1））。

请注意，“正确”答案通常还取决于询问的背景。