如何找到这种复杂性？

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

递归关系出现,f(n)= f(n-1)+ n,f(0)= 0因此复杂度大-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).