链表、数组、跳表时间复杂度
时间复杂度（流程决定）
何为常数时间的操作： 如果一个操作的执行时间不以具体样本呢量为转移，每次执行时间是固定时间，称这样的操作为常数时间的操作。
常见的常数时间操作：
- 常见的算数运算（+、-、*、/、%等）
- 常见的位运算（>>(带符号右移)、>>>(不带符号右移)、<<、|、&、^等）
- 赋值、比较、自增、自减操作等
- 数组寻址操作(访问数组中的每个元素时间都是一样的)
Linklist链表时间复杂度：
| 方法 | 复杂度 |
|---|---|
| prepend | O(1) |
| append | O(1) |
| lookup | O(n) |
| insert | O(1) |
| delete | O(1) |
Array数组时间复杂度
| 方法 | 复杂度 |
|---|---|
| prepend | O(1) |
| append | O(1) |
| lookup | O(1) |
| insert | O(n) |
| delete | O(n) |
跳表原理：添加索引:
思想：升维度、空间换时间
调表查询时间复杂度分析：
n/2、n/4、n/8、第k级索引结点个数就是n/(2k)，假设索引有h级，最高级索引有2个节点。n/(2h)=2,从而求得h = log2(n) - 1。
当增加、删除时，索引的位置会改变，维护成本比较高。
空间复杂度：O(n)
版权声明：本文为wfqiaodaima原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。