算法与数据结构（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
而 在第二个算法中则需要一个临时数组的辅助空间。此时空间复杂度为 n*1（n个元素的空间）