[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);
}
~~~
