[TOC]
# 简介
`O(1),O(n),O(lgn),O(nlogn),O(n^2)`
大O描述的是算法的运行时间和输入数据之间的关系
~~~
public static int sum(int[] nums) {
int sum = 0;
for(int num:nums) sum+= num;
return sum;
}
~~~
# `O(n)`
运行的时间和,n有关,是线性关系
n是nums中元素的个数
# 为什么用大O,叫O(n)?
忽略常数.实际时间`T=c1*n+c2`
~~~
T=2*n+2 O(n)
T=2000*n+10000 O(n) 渐进时间复杂度
T=1*n*n+0 O(n^2) 描述n趋近于无穷的情况
T=2*n*n+300n+10 O(n^2) 低阶项会被忽略
~~~
不一定O(n^2)就比O(n)慢
当n越大,O(n)的作用就体现出来了
# 分析动态数组的时间复杂度
## 添加操作
`addLast(e) O(1) 所消耗的时间是个常数`
`addFirst(e) O(n) 添加一个元素,其他元素都要向后移动一位,要看有多少元素,是线性关系`
`add(index,e) O(n/2)=O(n) 和index有关,index大和addLast(e)差不多,小和addFirst(e)差不多,需要概率论的一些知识`
这3个可以叫0(n)的算法,`addLast(e)`是O(1),但是我们一般都是看最坏的情况
resize那也就是0(n)的算法
## 删除操作
~~~
removeLast(e) 0(1)
removeFirst(e) O(n)
remove(index,e) O(n/2)=0(n)
~~~
这些也叫O(n)
## 修改操作
~~~
set(index,e) O(1)
~~~
## 查找操作
~~~
get(index) O(1) 已知索引查找
contains(e) O(n) 未知索引,要查找所有,找出来
find(e) O(n)
~~~
# 均摊复杂度
addLast(e)认为O(n)不一定合理
假设capacity=n,n+1次addLast,触发resize,总共进行2n+1次基本操作
平均,每次addLast操作,进行2次基本操作
这样均摊计算是O(1),均摊计算是比最坏计算有意义的
# 复杂度震荡
我们**同时**看**addLast和removeLast**操作
出现问题的原因:removeLast时resize过于着急(Eager)
解决方案:Lazy(懒惰)
当`size==capacity/4`时,才将capacity减半
所以缩容应该这样写
~~~
//如果数组中的利用少到一定的程度就把数据缩容
if (size == data.length / 4) {
resize(data.length / 2);
}
~~~
