1.0时间复杂度(斐波那契)
//计算阶层递归Fac的时间复杂度
long long Fac(size_t N)
{
if(0==N)
return 1;
return Fac(N-1)*N;
}
该算法的时间复杂度度很稳定:O(N)
//计算斐波那契数列递归Fib的时间复杂度
long long Fib(size_t N)
{
if(N<3)
return 1;
return Fib(N-1)+Fib(N-2);
}
F(N)=O(2^N);
斐波那契数列的递归写法完全是一个实际上没用的算法,因为运行速度很慢
2.0空间复杂度
定义:
- 空间复杂度也是一个数学函数表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。
- 空间复杂度不是程序占用了多少字节的空间,因为这个也没太大的意义,所以空间复杂度算的是变量的个数,也用大O渐进表示法
- 注:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显示申请的额外空间(比如 递归)来确定
//计算BubbleSort的空间复杂度?
void BubbleSort(int* a,int n)
{
assert(a);
for(size_t end=n;end>0;--end)
{
int exchange=0;
for(size_t=1;i<end;++i)
{
if(a[i-1]>a[i])
{
Swap(&a[i-1],&a[i]);
exchange=1;
}
}
if(exchange==0)
break;
}
}
空间复杂度:O(1)