以下功能的时间复杂度是多少?

Ish*_*hta 4 c c++ algorithm

    int func(int n){
       if(n==1)
         return 0;
       else
         return sqrt(n);
    }
Run Code Online (Sandbox Code Playgroud)

其中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在我最近出现的测试中得到了这个问题.

Dan*_*vil 5

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

我想说你可以认为它是“常数”,所以 O(1),从这个意义上说:如果你输入一个 random int,它平均会花费相同的时间。(原因:多位数字更为常见)。

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

这看起来像是教科书上的问题,而且可能是一个陷阱。老师可能想检查您是否能够区分计算sqrt数字列表(这将是 O(n))和单个数字(这将是 O(1))。

请注意,“正确”答案通常还取决于提问的上下文。

  • 所以在大多数算法的大多数实现中,复杂度是 O(1),因为输入受 32 或 64 位限制?我不认为这是这样的。当然,如果你的问题有自然的局限性,这是事实。 (2认同)

ami*_*mit 5

我将给出一些更一般的案例答案,而不假设大小不变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及其差异的更多信息,您可能需要查看此主题.

  • @IshitMehta理论上,在处理无界输入大小时,很多通常被认为是"O(1)"的东西都是"O(logN)".但是,很多时候我们可以绑定输入大小(int只有32-64位,例如...)我的回答是说它是一般情况的答案.有些东西仍然是"O(1)"而不管输入大小如何向链表添加元素,其中元素不必被复制 - 只是对它的引用(有限大小... ) (2认同)