算法与数据结构（2）--- 绪论（下）

第一部分 --- 基本概念和术语

1.数据类型和抽象数据类型

 

 将对变量的取值范围的约束和对变量的可进行操作的约束封装为数据类型，可以极大的方便人们进行编码

 

 

 

基本操作不就是函数吗 

 其实抽象数据类型就相当于C++中的 类

---

第二部分 --- 抽象数据类型的表示与实现

 

 抽象数据类型其实就相当于c++中的 类

---

第三部分 --- 算法和算法分析

1.算法的基本定义和性质

 一言以蔽之，算法就是我们解决问题的方法

1.所谓的二义性：既可以是a也可以是是b，这就称为二义性

2.一个算法可以没有输入，但是一定要有输出

 

 健壮性又称为鲁棒性

 

 

 

---

 2.算法分析之时间复杂度

算法分析的目的：1.分析一个算法是否可行；2.当一个问题可以通过多种算法解决的时候，通过算法分析找到最优算法去解决 

 1.所谓的矛盾是当我们想节省时间时会导致空间的消耗增加，节省空间时又会导致时间消耗增加

 我们常常采用事前分析法来估算算法消耗的时间和空间 

 

 注意有个求和符号

 

1.由于每个语句执行所需的时间与算法本身无关，所以我们可以将每个语句执行所需的时间视为单位时间，即为1，也就是说一个算法的效率只由它执行的语句总频率来进行估算和判断

上面这个n+1次：每执行一次循环都要先进行 i是否<=n 的判断然后再进行循环，判断语句执行n次后，i变为n+1，此时还要进行一次判断来终止循环，所以最终判断执行语句的执行次数为 n+1 次

 1.上面T1的算法的数量级是2次方，而T2是3次方，而时间数量级越小算法效率越高，所以我们选择T1算法  

2.上面那个辅助函数的通俗解释就是：f(n) = n的 t 次方（不一定，需要我们视具体情况来进行分析），n是问题规模n，即我们的算法要处理的元素个数，t是算法中执行次数最多（数量级最大）的语句的数量级

到底什么是基本语句 --- 基本语句就是算法中执行次数最多（数量级最大）的语句

 到底什么是问题规模n ---  问题规模n其实就是我们的算法要处理的元素个数

第三部分 --- 算法分析之如何找到时间复杂度对应的基础语句

1.基础语句基本都出现在最深层的循环嵌套中。

 时间复杂度算出来多少就是多少，不要随意更改符号

 

 有时候基础语句的语句频段并不是那么好求得比如上面这个，此时我们常常用下面那个级数求和的方式来求解语句频度：

1.j个1现加 = j

2. j从1开始，相加 = 等差数列求和

3. i从1开始相加 = 级数求和结果

各类级数收敛结果在这

根据具体情况分析时间复杂度（上面的处理方法是直接取对数） 

对数运算法则

有时候算法的时间复杂度还会因为问题的输入数据集不同而不同，此时我们取用的是时间复杂度是平均时间复杂度 

平均时间复杂度比较难求，所以我们一般考虑最坏时间复杂度

 

 指数爆炸

尽量设计复杂度低的算法

1.当算法中的被执行最多次的语句的次数是一个常数的时候，算法复杂度都为常数阶O (1)，哪怕你执行一次还是一百万次，只要你执行的是常数次那时间复杂度就是常数阶

2.算时间复杂度的时候 O 的括号中的 f(n) = 算法中被执行次数最多的语句的执行次数，但是光等于后放进来并没有结束：
如果 f(n)  = 一个常数，则令 f(n) 等于1；

如果 f(n)  = 多个变量相加，则令 f(n) = 所有变量中次方最大的那个变量，并且将这个变量的常数项去掉，如果每个变量的次方都一样的话，那就任取一个变量相等（并且要去掉常数项）

---

第四部分 --- 空间复杂度

 

在第一个算法中只需要一临时数组元素的辅助空间，所以空间复杂度为 1

而 在第二个算法中则需要一个临时数组的辅助空间。此时空间复杂度为 n*1（n个元素的空间）