溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
課前復習：
二分查找 時間復雜度（O(N))
空間復雜度：范圍最大的長度
復雜度：粗略衡量算法好壞的刻度尺（工具）
兩個維度：快慢 時間復雜度（重點）
使用空間的情況 空間復雜度
時間復雜度：直接利用允許時間衡量不現實，測試環境多變，不好控制變量
前提：如果指定cpu的情況下，單位時間內運行的基本指令個數是固定的
如果一個算法需要的指令比另一個算法需要的指令個數小，就可以推出算法A運行的時間更快
前提：算法計算的快慢和輸入的數據的規模是有關系的
粗略計算算法的快慢：
n:數據的規模
f（n）: n的數據規模情況下，需要的大概基本指令個數
引入大O漸進表示法：
1.只保留最高次項
2.保留的最高次項系數化為1
f(n)=2n+10
表示為O(n)
算法的快慢還和最好的情況，平均的情況，最好的情況
一般優先關注最壞的情況，其次平均情況，最好情況關注比較少
時間復雜度是o(log(n))
n 1000 1000 000 10億
o(n) 1000 1000 000 10億
o(log(n)) 10 20 30
常見的時間復雜度o(1) o(log(n)) 0(n) o(n*log(n)) o(n^2)
空間復雜度：
o(f(n)) 在輸入n規模下的情況下，算法需要的最大的空間情況
1‘開辟數組
2.畫調用棧
考慮 數組容量(array.length)和已有數據個數（size)的關系
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.發朋友圈
this.array=newArray;
4.老房子退掉
原來的數組對象，沒有引用指向，變成垃圾
擴容的空間越小，空間的浪費越小
擴容的空間越大，需要擴容的頻率越小
經驗值1.5或者2倍
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
