算法定义
- 是对特定问题求解步骤的一种描述，是指令的有限序列。
-
算法五大特征
- 输入：有0个或多个输入；
- 输出：有1个或多个输出；
- 有限性：算法有限步结束，指令有限时间完成；
- 确定性：每条指令有确切含义；
- 可行性：每个运算可由计算机有限条指令完成。
算法举例（递归）
定义
- 所谓递归，从字面意思可以看出有两个过程：“递去”和“归来”，即在“递去”过程中满足某个条件后进行“归来”。
- 绝大数编程语言支持函数的==自调用==，在这些函数可以通过调用自身来进行递归。
举例
- 整数n的阶乘（n！）
- 代码如下
long long recursion1(int n) //long long 类型防止结果溢出
{
if (n == 1 || n==0)
{
return 1;
}
return n * recursion1(n - 1);
}
// n=6---->返回720```
- 过程分析
| 函数 | 递去 |
是否满足if？ | 归来 |
|---|---|---|---|
| recursion1(6) | 否 | ||
| 否 | |||
| 否 | |||
| 否 | |||
| 否 | |||
| 是，开始归来 |
1 |
结果为720
递归与循环
- 我们首先引用知乎用户李继刚link对递归和循环的生动解释：
- 递归：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，==没有门了==。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。
- 循环：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门,==若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门==。但是，入口处的人始终等不到你回去告诉他答案。
- 对于一些简单的算法，与循环相比，我们可以直观的看出递归算法的==朴素与简洁==；
- 从算法本身出发，递归与循环并无优劣之分；但循环并不需要对函数进行重复调用，效率往往比递归效率高。
算法性能分析与度量
算法效率的评价方法
-
事后统计
- 将算法实现，统计其时间和空间开销；
-
事前分析
- 对算法所消耗时间和空间资源的一种估计方法。
算法效率分析——时间复杂度
==算法的运行时间==
==执行一次的时间==
指令系统、代码质量有关
定义
- 算法的运行时间可表示为基本语句执行次数，它是问题规模的函数；
- 称这个函数的==渐进阶==为算法的时间复杂度。
程序步
-
不严格的定义：
- 一个程序步是一个在语法上或语义有意义的程序片段，且该程序片段的执行时间不依赖实力特性。
各种语句的程序步数
- 注释语句：非执行语句，程序步数为0；
-
声明语句：程序步数为0；
- 定义变量和常量的语句（int、long、double等）
- 允许用户自定义数据类型（class、struct等）
- 判断访问权限的语句（private、public等）
- 描述函数特性的语句（void、virtual）
- 表达式和==赋值==语句：大部分程序步数为1，例外是表达式中包含函数调用；
- ==循环语句==：仅考虑语句中 ==控制部分== 的程序步数；
for(<初始化语句>;<表达式1>;<表达式 2>)
while<表达式>do
do...while<表达式>
- whille和do语句控制部分每次执行的程序步数等于<表达式>的程序步数;
- for语句的 ==控制部分== 每次执行步数都等于==1==，除非<初始化语句>、<表达式1>或<表达式 2>为实例性函数。
- ==注==：循环语句的程序步数为控制部分执行次数，而非循环执行次数，所以对于for(<初始化语句>;<表达式1>;<表达式 2>)和while<表达式>do语句来说，
;
而对于do...while<表达式>语句来说，因为是先执行后控制判断，所以。
- switch语句：由一个首部加上一个或多个条件语句组成。
switch(<表达式>)
{
case cond1:<语句1>
case cond2:<语句2>
...
default:<语句>
}
- 其中，首部 switch(<表达式>)的时间开销等于<表达式>的时间开销；每个条件语句的时间开销等于该条件语句自身==加上==其前面条件语句的时间开销。
-
if-else语句：由3部分构。
-
if(<表达式>)<语句1>; else<语句2>;每个部分程序步数分别根据<表达式>、<语句1>或<语句2>的程序步数来确定。
-
- 函数调用：==所有函数调用的程序步数都为1==，除非函数调用涉及与实例特性有关的按值参数传递。
- 内存管理语句：new、delete和sizeof，程序步数为==1==。
- 转移语句：包括continue,break,goto,return和return<表达式>，程序步数为==1==。除非<表达式>为 实例性函数。
计算程序步数的两种方法
实例如下，计算程序的程序步数：
float Sum(float * data, const int num)
{
float s = 0 ;
for(int i=0; i<num; i++){
s += a[i] ;
}
return s ;
}
- 全局count法：定义一个全局变量count初始为0，插入到程序中：
float Sum(float * data, const int num)
{
float s = 0 ;
count++ ;//变量s赋值
for(int i=0; i<num; i++){
count++ ;//for语句
s += a[i] ;
count++ ;//表达式
}
count++ ;//for语句最后一次控制判断
count++ ;//转移语句 return
return s ;
}
//进一步化简
float Sum(float * data, const int num)
{
for(int i=0; i<num; i++){
count +=2 ;
}
count +=3 ;
}
可见程序步数为 。
-
列表法：
| 行 | s/e | 语句频率 | 程序步数 |
|---|---|---|---|
| 1 | 0 | 1 | 0 |
| 2 | 1 | 1 | 1 |
| 3 | 1 | ||
| 4 | 1 | n | n |
| 5 | 1 | 1 | 1 |
| 6 | 0 | 1 | 0 |
| 总的程序步数 |
表示方法
-
-
；
- 给出算法复杂度上界，不可能比
更大。
- ==例==：
-
.
-
-
-
-
；
- 给出算法复杂度下界，不可能比
- ==例==：
-
.
-
-
-
-
；
- 给出算法复杂度下界和下界
- ==例==：
-
.
-
-
常用的时间复杂度
- ==大小比较==：
- ==指数时间的关系大小==：
- 一般的，常用 ==最深层循环内== 的语句中的原操作的执行频度（重复次数）来表示。
- 当
取的很大时，==指数时间算法和多项式时间算法在所需时间上非常悬殊==。
算法效率分析——空间复杂度
- 指算法在执行过程中所需最大存储空间;
- 空间复杂性的==渐进分析==：
.
- ==例==：
-
;
-
总结---基本概念
上一篇：数据结构-基本概念--数据
==思维导图==
在这里插入图片描述
