程序 = 数据结构 + 算法
数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科。
-
时间效率：算法执行所耗费的时间
-
空间效率：算法执行所耗费的存储空间
-
时间效率和空间效率有时候是矛盾的
-
度量方法
- 事后统计：将算法实现，测算其时间和存储空间开销
- 事前分析：对算法所消耗的资源的一种估算方法
事前分析
- 算法运行时间 = 一个简单操作所需的时间 x 简单操作次数
- 算法运行时间 = Σ 每条语句的执行次数 x 该语句执行一次所需的时间
for {i = 1; i < n; i ++}{ // 执行n+1次，其中n次进入循环体，最后一次执行完结束循环
for(j = 1; j < n; j++){ // 执行n*(n+1)次
c[i][j] = 0; // 执行n*n次
for(k = 0; k < n; k++){ //执行n*n*(n+1)次
c[i][j] = c[i][j] + a[i][k] * b[k][j]; // 执行n*n*n次
}
}
}若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
例： T(n) = 2n^3 + 3n^2 + 2n +1
当n -> ∞ 时，T(n) / n^3 -> 2，这表示n充分大时，T(n)和n^3同阶或同数量级，引入“O”记号，则T(n)可记作：T(n) = O(n^3)
i = 1; // 语句 1
while(i <= n>){
i = i * 2; // 语句 2
}
// 若循环执行1次，i = 1 x 2 = 2
// 若循环执行2次，i = 1 x 2 x 2 = 2^2
// 若循环执行3次，i = 1 x 2 x 2 x 2 = 2^3
// 若循环执行x次，i = 2^x
// 假设语句2执行x次，且循环条件为i <= n
// 则2^x <= n，则x <= log2 n随n的增大，不同数量级递增情况
| n | f(1) | f(logn) | f(n) | f(nlogn) | f(n^2) | f(n^3) | f(2^n) | f(n!) |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 1 | 2 | 1 |
| 2 | 1 | 1 | 2 | 2 | 4 | 8 | 4 | 2 |
| 4 | 1 | 2 | 4 | 8 | 16 | 64 | 16 | 24 |
| 8 | 1 | 3 | 8 | 24 | 64 | 512 | 256 | 40320 |
| 16 | 1 | 4 | 16 | 64 | 256 | 4096 | 65536 | 2.0923E+13 |
| 32 | 1 | 5 | 32 | 160 | 1024 | 32768 | 4.295E+09 | 2.6313E+35 |
算法所需存储空间的度量，记作：s(n) = O(f(n))
算法要占据的空间包含：
- 算法本身要占据的空间，输出/输出，指令，常数，变量等
- 算法要使用的辅助空间
// 将一维数组逆序
// 算法1
// 空间复杂度：S(n) = O(1)
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
// 算法2
// 空间复杂度：S(n) = O(n)
for(i = 0; i < n / 2; i++)
{
b[i] = a[n - i - 1];
}
for(i = 0; i < n; i++)
{
a[i] = b[i];
}
| 查找表头节点（首元节点） | 查找表尾节点 | 查找节点P的前驱节点 | |
|---|---|---|---|
| 带头节点的单链表L | L->next 时间复杂度O(1) |
从L->next依次向后遍历 时间复杂度O(n) |
通过p->next无法找到其前驱节点 |
| 带头节点仅设头指针L的循环单链表 | L->next 时间复杂度O(1) |
从L->next依次向后遍历 时间复杂度O(n) |
通过p->next可以找到其前驱节点 时间复杂度O(n) |
| 带头节点仅设尾指针R的循环单链表 | R->next 时间复杂度O(1) |
R 时间复杂度O(1) |
通过p->next可以找到其前驱节点 时间复杂度O(n) |
| 带头节点的双向循环链表L | L->next 时间复杂度O(1) |
L->prior 时间复杂度O(1) |
p->prior 时间复杂度O(1) |
| 比较项目 \ 存储结构 | 顺序表 | 链表 | |
|---|---|---|---|
| 空间 | 存储空间 | 预先分配，会导致存储空间闲置或溢出现象 | 动态分配，不会出现存储空间闲置或溢出现象 |
| 存储密度 | 不用为表示节点见的逻辑关系而增加额外的存储开销，存储密度=1 | 需要借助指针来体现元素间的逻辑关系，存储密度<1 | |
| 时间 | 存储元素 | 随机存取，按位置访问元素的时间复杂度为O(1) | 顺序存取，按位置访问元素时间复杂度为O(n) |
| 插入、删除 | 平均移动约表中一半元素，时间复杂度为O(n) | 不需要移动元素，确定插入、删除位置后，时间复杂度为O(1) | |
| 适用情况 | 1.表长变化不大，且能事先确定变化的范围 2.很少进行插入或删除操作，经常按元素位置序号访问数据元素 |
1.长度变化较大 2.频繁进行插入或删除操作 |
栈是一个特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表。
后进先出（LIFO）
进栈 Push
出栈 Pop
队列是一种先进先出的线性表，在表尾插入，在表头删除。 先进先出（FIFO）