Problem1546--计算时间复杂度

1546: 计算时间复杂度

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 23  Solved: 5
[Submit] [Status] [Web Board] [Creator:]

Description

计算下面这个递归函数的时间复杂度:

void fun(double n){//n>1
    if(n<=1)return;
    int m = pow(n,c);//n的c次方
    for(int i=0;i<m;++i)printf("%d ",i);
    for(int i=0;i<a;++i)fun(n/b);
}

Input

多组输入。
每组输入三个正整数a b c (b>1且a,b,c<10000)

Output

代码的时间复杂度。(数据保证时间复杂度为O(n^x)或O(n^xlogn)的形式,x保留4位小数)

Sample Input

4 2 2
5 2 2

Sample Output

O(n^2.0000logn)
O(n^2.3219)

HINT

可以试着先写出递归式再利用主定理求解。

Source/Category