绪论

数据结构的基本概念

数据: 是信息的载体, 分整数型与非整数型数据
数据项: 构成数据元素的最小不可分割单位, 如学生的成绩
数据元素: 数据的基本单位, 作为一个整体存储, 如每个学生的信息
数据类型: 具有相同性质的计算机数据的集合, 以及在这个集合上的一系列操作, 比如int、str、数组、类等, 分为简单类型(原子类型)和构造类型(结构类型), int、float等为简单类型, 数组、类等为构造类型

数据结构的定义: 按照某种逻辑关系组织起来的一组数据, 按一定的存储方式存储在计算机的存储器中, 并在这些数据上定义了一组运算的集合
数据结构的组成:

1. 逻辑关系
   1. 集合
   2. 线性关系
   3. 树结构
   4. 图结构
2. 存储方式
   1. 顺序存储
   2. 链式存储
3. 对数据的操作

算法的基本概念

算法分析

算法的五个要素:

1. 输入
2. 输出
3. 有穷性
4. 确定性
5. 可行性

描述算法的方法:

1. 自然语言
2. 流程图
3. 伪代码
4. 程序设计语言

评价算法的方法:时间复杂度、空间复杂度、鲁棒性.....

时间复杂度

算法的频度：每条代码执行的次数
算法的时间耗费：各条代码执行的总次数
时间复杂度O( ): 括号中为对时间耗费影响最大的因子，可以为\(n^2、n^k、log_2n、n! .....\)等

NP问题

P问题(多项式时间问题): 能找到一个能在多项式的时间里解决它的算法的问题, 这种算法叫多项式时间算法。另一类为指数时间算法, 其时间复杂度不能用多项式函数界定

NP问题: 不确定能否在多项式时间内找到一个解, 但能在多项式时间内验证一个解(也就是说不一定存在一个多项式解决算法, 但存在多项式检查算法)

NP完全问题(NPC问题): 每一个可能解都可以在多项式时间内验证的NP问题