时间复杂度
算法执行时间与数据规模之间的增长关系。
越来越复杂：常对幂指阶
数组
-
为什么下标从零开始？
方便寻址地址的计算，从1开始的话寻址就会多一步-1的运算。
对于CPU来说多了一步减法指令。 -
时间复杂度
-
索引查找
O(1) -
内容查找
O(n) -
插入复杂度
O(n)
-
-
面试题
-
数组转list Arrays.aslists，数组中的元素变动会影响list么？
会；数组属于引用传递。 -
list 使用 list.toArray转数组后，list变动会影响数组么？
不会；使用了System.arrayCopy；属于两个对象了，所以不会有影响。
-
链表
时间复杂度
-
查找
O(n) -
插入复杂度(插入头结点)
O(1)
红黑树
自平衡的二分查找树（O(logn)）
- 根节点都是黑色
- 红节点的子节点都是黑色
- 叶子结点都是黑色的null节点
- 每个分支上的黑节点个数是一样的
散列表
key,value结构，拉链法解决hash冲突问题。
-
key
经过hash计算以及求模存入定位到数组索引。 -
key，value
-
追加到链表之后
当链表长度大于8，链表则变为红黑树（jdk1.8之后）扩容后树的节点数小于等于6，退化成链表。