文档介绍：二级公共基础知识
第一章数据结构基础
内容提要
算法:算法的基本概念、算法复杂度
数据结构的基本概念:什么是数据结构、数据结构的图形表示、线性结构与非线性结构
线性表及其顺序存储结构:线性表的基本概念、顺序存储结构、插入运算、删除运算
栈和队列:栈及其基本运算、队列及其基本运算
线性链表:基本概念、基本运算、循环链表及其基本运算
树与二叉树:树的基本概念、二叉树及其基本性质、二叉树的存储结构、二叉树的遍历
查找技术: 顺序查找、二分法查找
排序技术:交换类排序法、插入类排序法、选择类排序法
2
算法
算法的基本概念
算法是解题方案的准确而完整的描述,它不等于程序,也不等计算方法。
可行性(effectiveness)
确定性(definiteness)
有穷性(finiteness)
拥有足够的情报
算法中对数据的运算和操作
算术运算:包括加、减、乘、除等)
逻辑运算:包括“与”、“或”、“非”等运算)
关系运算:包括“大于”、“小于”、“等于”、“不等于”等)
数据传输:包括赋值、输入、输出等操作
算法的控制结构
4
算法的基本概念
列举法
归纳法
递推
递归
减半递推技术
回溯法
5
算法复杂度
算法复杂度:时间复杂度、空间复杂度
执行算法所需要的计算工作量
与下列因素有关:
书写算法的程序设计语言
编译产生的机器语言,代码质量
机器执行指令的速度
问题的规模
6
算法复杂度
问题的规模函数
算法的工作量=f(n)
算法中基本操作重复执行的频率T(n),是问题规模n的某个函数f(n),记作:
T(n)=O(f(n))
记号“O”读作“大O”。表示随问题规模n的增加,算法执行时间的增长率和f(n)相应增加。
常见算法复杂度:
O(1):常数阶 O(n):作线性阶 O(n2):平方阶
O(n3):立方阶 O(logn):对数阶 O(2n):指数阶
7
算法复杂度
n×n矩阵相乘算法:
时间复杂度为O(n3)。
8
算法复杂度
分析算法的工作量两种方法:
平均性态
最坏情况复杂性
9
算法复杂度
算法执行过程中所需的最大存储空间
存储量包括以下三部分
算法程序所占的空间
输入的初始数据所占的存储空间
算法执行过程中所要的额外空间
算法空间复杂度可定义为:
S(n)=O(f(n))
原地工作(in place)的算法:记作O(1)
压缩存储技术
10