java數(shù)據(jù)結(jié)構(gòu)知識點(diǎn)自我總結(jié)

課前復(fù)習(xí)：
二分查找 時(shí)間復(fù)雜度（O(N))
空間復(fù)雜度：范圍最大的長度
復(fù)雜度：粗略衡量算法好壞的刻度尺（工具）
兩個(gè)維度：快慢 時(shí)間復(fù)雜度（重點(diǎn)）
使用空間的情況 空間復(fù)雜度
時(shí)間復(fù)雜度：直接利用允許時(shí)間衡量不現(xiàn)實(shí)，測試環(huán)境多變，不好控制變量
前提：如果指定cpu的情況下，單位時(shí)間內(nèi)運(yùn)行的基本指令個(gè)數(shù)是固定的
如果一個(gè)算法需要的指令比另一個(gè)算法需要的指令個(gè)數(shù)小，就可以推出算法A運(yùn)行的時(shí)間更快
前提：算法計(jì)算的快慢和輸入的數(shù)據(jù)的規(guī)模是有關(guān)系的
粗略計(jì)算算法的快慢：
n:數(shù)據(jù)的規(guī)模
f（n）: n的數(shù)據(jù)規(guī)模情況下，需要的大概基本指令個(gè)數(shù)
引入大O漸進(jìn)表示法：
1.只保留最高次項(xiàng)
2.保留的最高次項(xiàng)系數(shù)化為1
f(n)=2n+10
表示為O(n)
算法的快慢還和最好的情況，平均的情況，最好的情況
一般優(yōu)先關(guān)注最壞的情況，其次平均情況，最好情況關(guān)注比較少

時(shí)間復(fù)雜度是o(log(n))
n 1000 1000 000 10億
o(n) 1000 1000 000 10億
o(log(n)) 10 20 30
常見的時(shí)間復(fù)雜度o(1) o(log(n)) 0(n) o(n*log(n)) o(n^2)

空間復(fù)雜度：
o(f(n)) 在輸入n規(guī)模下的情況下，算法需要的最大的空間情況
1‘開辟數(shù)組
2.畫調(diào)用棧

考慮 數(shù)組容量(array.length)和已有數(shù)據(jù)個(gè)數(shù)（size)的關(guān)系
1.容量是夠用的size<array.length
2.容量不夠用
搬家（1.5、2倍）
int newCapacity=array.length*2;
1.找新家;
int[] newArray=new int[newCapacity]
2.搬家
for(int i=0;i<size;i++){
newArray[i]=array[i];
}
3.發(fā)朋友圈
this.array=newArray;
4.老房子退掉
原來的數(shù)組對象，沒有引用指向，變成垃圾
擴(kuò)容的空間越小，空間的浪費(fèi)越小
擴(kuò)容的空間越大，需要擴(kuò)容的頻率越小
經(jīng)驗(yàn)值1.5或者2倍