考研-数据结构2-算法和算法的复杂度

算法是对问题求解步骤的描述，通过有序序列的指令来实现

五大特征
1.有穷性:有限步之后结束不会出现无限循环
2.确定性:不存在二义性,算法的每个步骤精确定义
3.可行性:比如受限于计算机的计算能力，有的算法虽然理论上可行，但实际上无法完成
4.输入：能被计算机处理的各种类型数据,如数字，音频，图像等
5.输出：一至多个程序输出结果

算法的复杂度
时间复杂度
·衡量算法随之问题规模增大，算法执行时间增长的快慢
·时间复杂度是问题规模的函数，记作T(n)，时间复杂度主要分析T(n)的数量级
·T(n)=O(f(n))，大O记法，f(n)是算法中基本运算的频度，一般考虑最坏情况下的时间复杂度

·计算方法:去算法时间增长最快的那个函数项，把它的系数改为1
空间复杂度
·衡量算法随之问题规模增大，算法执行空间增长的快慢
·是问题规模的函数：S(n) = O(g(n))

时间复杂度的计算

结论
·复杂度是关于增长率的，所以可以直接会忽略常数项。
·一般可以直接关注循环段最基本操作语句的执行次数

时间复杂度计算(多个循环体)
运算规则：乘法规则，加法规则。

空间复杂度
·空间复杂度S(n)之算法运行中所使用的辅助空间的大小。
记为:

S(n) = O(f(n))

·辅助空间:处理存储算法本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。
·算法原地工作是指算法所需的辅助空间是常量，即O(1)。
·考研中出现O(1),O(n)较多