包含另一个函数的函数的时间复杂度

Question

谁能详细解释一下这段代码的时间复杂度怎么算？

int f(int n)
{
    int sum = 0;
    while (n>1)
    {
        sum +=g(n)
        n = sqrt(n)
    }
    return sum;
}

其中 g(n) 由下式给出：

int g(int n)
{
    int sum  = 0;
    for (int i = 1; i<n; i*=2)
        sum +=i;
    return sum;
}

提前致谢！

Answer 1

g 是它的参数的对数（如果你传递它 n，它的循环重复 log[2](n) 次，因为它需要多次迭代才能使 i 达到 n.

f 是双对数 - 它在每个操作中将 n 的指数减半，重复 log[2](log[2](n))。

我们可以忽略 g 是一个单独的函数这一事实 - 实际上，它是一个嵌套在另一个循环中的循环。如果我们准确分析 g 的重复次数如何随着 f 的进行而减少，我们可以找到更好的限制，但是 O(log n * log log n) 已经足够好了。（复杂性理论就像海鲜：虽然 "I ate bluefin tuna" 可能是的正确答案，但 "I ate fish" 并没有错。）

编辑：

However the right answer is O(log(n)) (final test answer) and I don't understand why....

正如我所说：

We can find a better limit if we analyse exactly how the number of repetitions of g decreases as f progresses

但老实说，从结果比代码更容易做到这一点。假设 n 从 65536 开始。这将为我们提供 g 的 16 次迭代。它的根是 256，这将允许 g 到运行 8 次。接下来是 16，g 的 4 次迭代。然后4为2，2为1。这看起来像一个几何级数：16+8+4+2+1 = 32-1，其中32是2 * log[2](65536)，符合O(log n)。

或者您可能会注意到在 f 的第一次迭代中会有很多 g 的迭代，与之相比 g 的所有其他调用都是无关紧要的（以对数方式消失）。由于 g 的第一次调用是 O(log(n))`，我们可以在那里 t运行并说这就是复杂性。

Answer 2

稍微具体一点的证明方法：

正如之前正确回答的那样，g(n) 的复杂度是 O(log n)。 g(n) 中的循环执行的精确次数是 floor(log2(n)) + 1.

现在 f(n)。在第 m 次循环迭代后 n 的值，相对于 n 的原始值，是：

由此，使用循环条件n > 1，本次循环执行的次数为：

这样可以将 f(n) 的复杂度函数表示为求和：

在 (*) 中，我使用了这样一个事实，即向下舍入的数字与其原始值仅相差小于而不是 1（因此 O(1)）。在 (**) 中，我使用了几何级数和的标准结果。

(**)中划线项的2的负次方。当n趋于无穷大时，此项消失，所以划线项本身收敛于2。

因此最终的复杂度仅为 O(log n + log log n) = O(log n)，因为第一项占主导地位。

Answer 3

描述函数渐近行为的大 O 符号。基本上，它告诉您函数增长或下降的速度

例如，在分析某些算法时，可能会发现完成大小为 n 的问题所需的时间（或步数）由

给出

T(n) = 4 n^2 - 2 n + 2

如果我们忽略常量（这是有道理的，因为它们取决于程序运行所在的特定硬件）和增长较慢的项，我们可以说 "T(n)" 以 n^ 的顺序增长2 " 和 write:T(n) = O(n^2)

对于正式定义，假设f(x) 和g(x) 是定义在实数的某个子集上的两个函数。我们写

f(x) = O(g(x))

（或 f(x) = O(g(x)) for x -> infinity 更精确）当且仅当存在常数 N 和 C 使得

|f(x)| <= C|g(x)| for all x>N

直觉上，这意味着 f 的增长速度并不比 g

如果a是实数，我们写

f(x) = O(g(x)) for x->a

当且仅当存在常数 d > 0 和 C 使得

|f(x)| <= C|g(x)| for all x with |x-a| < d

所以你的情况是

O(n) as |f(x)| > C|g(x)|

引用自http://web.mit.edu/16.070/www/lecture/big_o.pdf

for r from 0 to xlist:  // --> n time
       for c from 0 to ylist: // n time
         sum+= values[r][c]  
         n+1

}

Big O Notation gives an assumption when value is very big outer loop will run n times and inner loop is running n times

Assume n -> 100 than total n^2 10000 run times

包含另一个函数的函数的时间复杂度

Time Complexity of function that contains another function

time

complexity-theory

for-loop

while-loop