基本概念
- 数据：数据是可被计算机识别并加工处理的对象。
- 数据元素：数据元素是由数据组成的具有一定意义的基本单位
- 数据项：是组成数据元素的、不可分割的最小单位。
- 数据结构：由某一数据对象及该对象中所有数据元素之间的关系组成的。
数据结构
数据的逻辑结构
- 线性结构
- 树形结构
- 图结构
- 集合结构
数据的存储结构
- 顺序存储结构 （数组）
- 链式存储结构 （链表）
数据的运算：增、删、改、查
数据类型：整形，字符型，指针等
抽象数据类型
数据封装
信息隐蔽
算法
算法概念
- 五个特征
- 输入：一个算法有 0 个或多个输入。
- 输出：一个算法产生一个或多个输出，作为算法运算的结果。
- 可行性：算法的每一个步骤都可以通过已经实现的基本运算来实现。
- 确定性：算法的每一个步骤都必须有确切的含义，不会产生二义性。
- 有穷性：算法必须能在执行有穷步之后终止。
- 四个衡量标准
- 正确性
- 可读性
- 健壮性
- 高效性
- 算法的时间复杂度
- 常见时间复杂度：O(1)＜O(log2 n)＜O(n)＜O(nlog2 n)＜O(n2)＜O(n3) 。
- 最坏、最好和平均情况时间复杂度
- 最好情况：待搜索的元素 x 正好是第一个元素
- 最坏情况：待搜索的元素 x 是最后一个元素或是不在数组中
- 平均情况：需要多次在数组中查找元素，以相等的概率查找每个数组元素
- 算法的空间复杂度
- 固定部分：主要包括程序代码、常量、简单变量等所占的空间。
- 可变部分：算法执行所需的额外空间，如递归栈所用的空间。