c - 如何找到这种复杂性？

Question

如果我有以下形式的函数，

int foo ( int n )
{
    if ( n == 0 )
        return 0;
    else
     return n + foo ( n-1)
}

使用 big-O 调用 foo(foo(n)) 的运行时间是多少。

递推关系为:f(n) = f(n-1) + n, f(0) = 0 因此复杂度是大O(n^2)。但是如何做到以上呢？

Answer 1

The recurrence relation is coming out to be, f(n) = f(n-1) + n, f(0) = 0 And therefore complexity is big-O(n^2).

实际上，foo函数的复杂度是O(n)，因为你只是从n开始倒数，调用该函数时n - 1 并将结果添加到 n。

现在，foo 返回的值是O(n^2)，因为该函数计算总和1 + 2 + ... + n，即 n(n+1)/2。

所以，我们有:

foo(foo(n)) = foo(something that is O(n^2)) = O(n^2)

因为外部 foo 的参数是线性的，即 O(n^2)。