数据的逻辑结构与存储结构的基本概念
逻辑结构分为四种类型
集合结构：元素同属一个集合，元素之间没有什么关系。
线性结构： 典型的有顺序表，链表，栈和队列。 元素之间是一对一关系。
树形结构：二叉树，元素之间是一对多关系
图形结构：有向图与无向图。元素之间是多对多的关系。
物理结构（又称存储结构）分为两类
顺序结构：元素在连续的存储单元中，物理顺序与逻辑顺序是一致的，比如数组。优点是访问速度快，缺点是插入和删除操作耗时久。
链式结构：元素可以在不连续的存储单元中，通过指针指向前驱节点或者后驱节点，有点是插入和删除都很快。
算法的定义、基本性质以及算法分析的基本概念，包括采用大O形式表示时间复杂度和空间复杂度
算法的定义：是为了求解问题给出的有限指令序列，每条指令表示一个或多个操作。
算法的基本性质：
输入：一个算法有0个或多个输入，这些输入取自某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出是同输入具有某种特定关系的量
确定性：算法中每一条指令必须有确切的含义，不具有二义性
可行性：算法中描述的操作都可以用已经实现的运算执行有限次来实现。
有穷性：一个算法必须能够在执行又穷步骤后结束，并且每一步都能在又穷时间内完成。
算法分析
：算法运行所需要的时间称为时间复杂性；算法运行所需要的辅助空间称为空间复杂性
事前估计法：时间按复杂度估计。 抽象过程如下：算法运行时间=每条语句执行时间之和-》每条语句的执行次数之和-》基本语句的执行次数-》基本语句执行次数的数量级-》大O号表示。常见的时间复杂度如下Ο(1)＜Ο(log₂n)＜Ο(n)＜Ο(nlog₂n)＜Ο(n²)＜Ο(n³)＜…＜Ο(2ⁿ)＜Ο(n!)
描述
增长的数量级
典型代码
说明
举例
常数级别
Ο(1)
a=b+c
普通语句
将两个数相加
对数级别
Ο(log₂n)
二分查找
二分查找
二分查找
线性级别
Ο(n)
for(int i=0;i } 循环 找出最大元素 线性对数级别 Ο(nlog₂n) 分治 归并排序 平方级别 Ο(n²) for(int i=0;i for(int j=0;j } } 双层循环 检查所有元素对 立方级别 Ο(n³) 代码省略 三层循环 检查所有三元组 指数级别 Ο(2ⁿ) 穷举查找 检查所有子集 事后统计法：程序运行测试。 比如在调用某个方法的前后打印当前时间，以此来判断该方法执行耗时，缺点是需要编写特定程序，且硬件环境影响测试结果（比如服务器与pc机器性能不同，同样的算法在这2者之间运行的时间是不一样的）