-
- 算法的特性
- 时间复杂度
- 空间复杂度
算法的特性
1. 有穷性：由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止
2. 确定性：每条语句有确定的含义，无歧义
3. 可行性：在当前环境条件下可以通过有限运算实现
4. 输入输出：有零个或多个输入，一个或多个输出
“好”算法的标注如下
1. 正确性：满足具体问题的需求，程序运行正常无语法错误，能通过软件测试，达到预期的需求
2. 易读性：标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改
3. 健壮性：对于非法数据及操作有较好的反应和处理
4. 高效性：指算法运行效率高，即算法运行所消耗的时间短。因此我们将算法基本运算的执行次数作为时间复杂度的衡量标准
5. 低存储性：低存储性是指算法所需要的存储空间低。因此算法占用的控件大小称为空间复杂度
时间复杂度
定义：算法运行需要的时间，一般将算法的执行次数作为时间复杂度的度量标准
//算法1_1
sum=; //运行1次
total=; //运行1次
for(i=;i<=n;i++){ //运行n次
sum+=i; //运行n次
for(j=;j<=m;j++){ //运行n*n次,嵌套循环
total+=i*j; //运行n*n次
}
}
T（n）=++n+n+n*n+n*n
备注：运行次数中有高次方时，一般以最高次方来计算算法的运行时间
备注：在算法分析中，渐近复杂度是对算法运行次数的粗略估计，大致反映问题规模增长趋势，而不必精确计算算法的运行时间，在计算渐近时间复杂度时，可以只考虑对算法运行时间贡献最大的语句，而忽略那些运算次数少的语句。循环语句中处在循环内层的语句往往运行次数最多
不是每个算法都能直接计算运行次数
如下算法1_2
findx(int x){
foor(int i=;i<n;i++){ //在a[n]数组中顺序查找x
if(a[i]==x)
return i; //返回其下标i
}
return -;
}
此类型算法我们就很难计算其到底执行了多少次，因为这依赖于i在数据中的位置，所以我们只能计算其平均执行次数为（n+1）/2
有些算法，如排序，查找，插入等算法，可以分为最好，最坏和平均情况分别求算法渐近复杂度，但是我们考察一个算法通常考察最坏的情况，而不是最好的情况
空间复杂度
定义：算法占用的空间大小，一般将算法的辅助空间作为衡量空间复杂度的标准，主要包括三部分
1. 输入/输出数据
2. 算法本身
3. 额外需要的辅助空间
算法1_3
//将两个数交换，并分析其空间复杂度
swap（int x,int y）{ //x与y交换
int temp;
temp=x; //此时temp为辅助空间
x=y;
y=temp;
}
该算法使用了一个辅助空间temp，空间复杂度为O（1）
注意：递归算法中，每一次递推需要一个栈空间来保存调用记录，因此空间复杂度需要计算递归栈的辅助空间
算法1_4
fac(int n){
if(n<){ //小于零的数无阶乘值
printf("n<0,data error!");
return -;
}else if(n== || n==){
return ;
}else{
return n*fac(n-);
}
}
递推与回归过程如下图：
此时，计算机内部是使用一种称为“栈”的数据结构，其特性为不允许中间插入或抽取，因此称为“后进先出”
因为划分栈空间的数量取决于n的值，所以此算法的空间复杂度为O(n)，时间复杂度也为O(n)
n爆炸增量问题
一棋盘麦子故事告诉我们，当高次方到达一定程度，会出现爆炸性增长，如2的64次方达到了将近7730亿，假如算法的时间复杂度达到了O(2^n)会怎么样？
常见的算法时间复杂度有一下几类
1. 常数阶：常数阶的算法运行的次数是一个常数
2. 多项式阶：很多算法时间复杂度是多项式，通常用O(n)，O(n^2)表示
3. 指数阶：指数阶时间复杂度运行效率极差，O(2^n)使用这样的算法要慎重
4. 对数阶：对数阶时间复杂度运行效率较高，常见的有O(logn)，O(nlogn)
从指数阶增量随着x的增加而急剧增加，而对数阶增加缓慢，他们之间的关系为：
O(1)
Fib1(int n){
if(n<){
return -;
} if(n== || n==){
return ;
return Fib1(n-)+Fib1(n-);
}
}
//算法复杂度
n=时，T(n)=;
n=时，T(n)=;
n=时，T(n)=; //调用Fib1(2),Fib(1)和执行一次加法运算Fib1(2)+Fib1(1)
算法改进，算法1_6
既然斐波那契数列中的每一项是前两项之和，如果记录前两项的值，只需要一次加法运算就可以得到当前项，我们可以用数组
Fib2(int n){
if(n<){
return -;
}
int *a=new int[n];
a[]=;
a[]=;
for(int i=;i<=n;i++){
a[i]=a[i-]+a[i-];
}
return a[n];
}
很明显，时间复杂度为O(n)
此算法使用了一个辅助数组记录中间结果，空间复杂度也为O(n)，其实我们只需要得到第n个斐波那契数，直接结果只是为了下一次使用，根本不用记录下来，因此我们可以采用迭代法进行算法设计
算法1_7
Fib3(int n){
int i,s1,s2;
if(n<){
return -;
}if(n== || n==){
return ;
}
s1=;
s2=;
for(i=;i<=n;i++){
s2=s1+s2; //辗转相加法
s1=s2-s1;//记录前一项
}
return s2;
}
迭代过程如下：
此算法使用了若干个辅助变量，迭代辗转相加，每次记录前一项，时间复杂度为O(n)，但空间复杂度降到O(1)
我们还能继续降阶么？可以，最多可以降到对数阶O(logn)