以下函数的时间复杂度是多少？ [英] What is the time complexity of the following function?

问题描述

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

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

Where sqrt(n) is a C math.h library function.

1. O（1）


2. O（lg n）

> O（lg lg n）

3. O（n）

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

时间完全取决于sqrt（n）。但是，我不知道这个函数是如何实际实现的。

I think that the running time entirely depends on the sqrt(n). However, I don't know how this function is actually implemented.

找到我知道的数字的平方根的一般方法是使用牛顿的方法。如果我没有错，使用牛顿的方法的时间复杂度证明是O（lg n）。所以，答案应该是O（lg n）？

P.S. The general approach towards finding the square root of a number that I know of is using Newton's method. If I am not wrong, the time complexity using Newton's method turns out to be O(lg n). So should the answer be O(lg n)?

P.P.S。在最近的测试中，我出现了这个问题。

P.P.S. Got this question in a recent test that I appeared for.

推荐答案

我将给出一个更一般的情况下的答案，不假设常量大小 int 。

I am going to give a bit more general case answer, without assuming constant size of int.

答案是 Theta（logn）。

我们知道newton-raphson是Theta（logn） - 排除 Theta（n）（假设 sqrt / code>尽可能高效。

We know newton-raphson is Theta(logn) - that excludes Theta(n) (assuming sqrt() is as efficient as we can).

但是，一般的数字 n requries log_2（n）位编码 - 你需要读取它以获得准确的 sqrt（）功能。这不包括 Theta（1）和 Theta（log（log（n））。

However, a general number n requries log_2(n) bits to encode - and you require to read all of it in order to get an accurate sqrt() function. This excludes Theta(1) and Theta(log(log(n)).

从上面我们可以知道函数的复杂度是 Theta（log（n））。

From the above, we know that the complexity of the function is Theta(log(n)).

另一方面，由于 O（log（n））是 O（n） - 它也是一个有效的答案，虽然不紧。有关大Theta和大O及其差异的更多信息，你可能想看看此主题。

As a side note, since O(log(n)) is a subset of O(n) - it is also a valid answer, though not tight one. For more information about big Theta and big O and their differences, you might want to have a look on this thread.

这篇关于以下函数的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！