逻辑结构和物理结构
逻辑结构
- 集合结构：同属一集合，之间没有关系
- 线性结构：一对一关系，有顺序
- 树形结构：一对多的层次关系
- 图形结构：多对多的关系
物理结构
- 顺序存储：地址连续，逻辑关系与物理一致
- 链接存储：任意存储单元，可连续，也可不连续
算法时间复杂度
渐进增长
在输入规模n没有限制的条件下，只要超过一个数值N，这个函数就总大于另一个函数，我们称函数是渐进增长的。
函数的渐进增长
给定两个函数f(n)和g(n)，如果存在一个整数N，是的对所有的n>N，f(n)总是比g(n)大，那么就说：f(n)的增长渐进快于g(n)。
时间复杂度
时间复杂度考虑的是渐进增长。如：O(n^3)>O(n^2+100)
常见时间复杂度：
O(1) 常数
O(logn) 对数
O(n) 线性
O(nlogn) nlog(n)
O(n^2) 平方
O(n^3) 立方
O(2^n) 指数
O(n!) 阶乘
O(n^n)
最后三个，除非n非常小，哪怕n=100，都是噩梦般的运行时间。这种不切实际的复杂度，一般不讨论。
线性表
零个或多个元素的有限序列。是有顺序的，有前驱、后继元素。
有顺序存储结构和链式存储结构两种。
顺序存储
用一段地址连续的存储单元依次存线性表的数据元素。
插入删除
最好（最后一位）：O(1)
最坏（第0位）：O(n)
平均：插到第i位，移n-i
存、读：O(1)
插、删：O(n)
优点：
- 无须为表中元素之间的逻辑关系增加额外存储空间。
- 可快速存取表中任意位置的元素。
缺点：
- 插、删需要移动大量元素
- 长度变化较大时，难以确定存储空间容量
- 易造成存储空间的碎片。
链式存储结构
存储单元可以连续，也可以不连续。
单链表
头指针是必须的，头结点不是。