时间复杂度和空间分析
目录
1.算法效率
算法效率分析分为两种：一是时间效率，二是空间效率。时间效率被称为时间复杂度，而空间效率被称为空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。
2.时间复杂度
1.概念
定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
2.大O的渐进表示法
计算一下Func1基本操作执行了多少次？
void Func1(int N)
{
int count=0;
for(int i=0;i<N;++i)
{
for(int j=0;j<N;++j)
{
++count;
}
}
for(int k=0;k<2*N;++k)
{
++count;
}
int M=10;
while(M--)
{
++count;
}
printf("%d\n",count);
}
Func1执行的基本操作次数：
F（N）=N^2+2*N+10
实际中我们计算时间复杂度不一定要计算精确的执行次数，而只需要大概执行次数，那么我们可以使用大O的渐进表示法。
大O符号：
适用于描述函数渐进行为的数学符号
推导大O阶方法：
- 用常熟1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O阶的渐进表示法以后，Func1的时间复杂度为：O(N^2)
3.常见时间复杂度计算举例
例1：
void Func2(int N)
{
int count=0;
for(int k=0;k<2*N;++K)
{
++count;
}
int M=10;
while(M--)
{
++count;
}
printf("%d\n",count);
}
Func2 的时间复杂度为：基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为O(N)
例2：
void Func3(int N,int M)
{
int count=0;
for(int k=0;k<M;++k)
{
++count;
}
for(int k=0;k<N;++k)
{
++count;
}
printf("%d\n",count);
}
Func3 的时间复杂度为：O（M+N)
例3：
void Func4(int N)
{
int count=0;
for(int k=0;k<100;++k)
{
++count;
}
printf("%d\n",count);
}
Func4 的时间复杂度为：通过推导大O阶方法，时间复杂度为O（1）
例4：
const char * strchr(const char *str,int character);
Func5的时间复杂度为：基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为O(N)
例5：
void BubbleSort(int *a,int n)
{
assert(a);
for(size_t end=n;end>0;--end)
{
int exchange=0;
for(size_t i=1;i<end;++i)
{
if(a[i-1]>a[i])
{
Swap(&a[i-1],&a[i]);
exchange=1;
}
}
if(exchange==0)
break;
}
}
时间复杂度为：基本操作最好执行N次，最坏执行（N*(N+1)/2次，因此时间复杂度为O(N^2)
例6：
int BinarySearch(int *a,int n,int x)
{
assert(a);
int begin=0;
int end=n-1;
while(begin<end)
{
int mid=begin+((end-begin)>>1);
if(a[mid]<x)
begin=mid+1;
else if(a[mid]>x)
end=mid;
else
return mid;
}
return -1;
}
时间复杂度为：O(logN)
例7：
long long Factorial(size_t N)
{
return N<2 ? N:Factorial(N-1)*N;
}
时间复杂度为：O(N)
例8：
long long Fibonacci(size_t N)
{
return N<2 ? N:Fibonacci(N-1)+Fibonacci(N-2);
}
时间复杂度为：O(2^N)
3.空间复杂度
1.定义
空间复杂度是一个算法在运行过程中临时占用存储空间大小的量度。计算规则基本跟时间复杂度类似，也用大O渐进表示法。
2.实例
- 计算BubbleSort的空间复杂度
void BubbleSort(int *a,int n)
{
assert(a);
for(size_t end=n;end>0;--end)
{
int exchange=0;
for(size_t i=1;i<end;++i)
{
if(a[i-1]>a[i])
{
Swap(&a[i-1],&a[i]);
exchange=1;
}
}
if(exchange==0)
break;
}
}
空间复杂度为：使用了常数个额外空间，所以空间复杂度为O(1)
- 计算Fibonacci的空间复杂度
long long *Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long *fibArray=new long long [n+1];
fibArray[0]=0;
fibArray[1]=1;
for(int i=2;i<=n;++i)
{
fibArray[i]=fibArray[i-1]+fibArray[i-2];
}
return fibArray;
}
空间复杂度为：O(N)
- 计算阶乘递归Factorial的空间复杂度
long long Factorial(size_t N)
{
return N<2? N:Factorial(N-1)*N;
}
空间复杂度为：O(N)
（注：部分内容来源网上）
转载自：https://blog.csdn.net/D_4_Y_/article/details/82999091
