算法復雜度作用
數據結構和算法本身解決的是“快”和“省”的問題，即如何讓代碼運行得更快淫茵，如何讓代碼更省存儲空間。所以财破，執(zhí)行效率是算法一個非常重要的考量指標宗挥。
多項式階：隨著數據規(guī)模的增長乌庶，算法的執(zhí)行時間和空間占用，按照多項式的比例增長契耿。包括瞒大，
O(1)（常數階）、O(logn)（對數階）搪桂、O(n)（線性階）透敌、O(nlogn)（線性對數階）、O(n^2 )（平方階）锅棕、O(n^3 )（立方階）
- 非多項式階：隨著數據規(guī)模的增長拙泽，算法的執(zhí)行時間和空間占用暴增，這類算法性能極差裸燎。包括顾瞻，O(2^n )（指數階）、O(n!)（階乘階
- 算法時間復雜度由小到大依次為：Ο(1)＜Ο(logn)＜Ο(n)＜Ο( nlog^n )＜Ο( n^2 ) ＜Ο( n^3 ) ＜…＜Ο( 2^n ) ＜Ο(n!)
[圖片上傳失敗...(image-516b81-1554175993123)]
空間復雜度
先說空間復雜度德绿，因為空間復雜度比較簡單
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
第 2 行代碼中荷荤，我們申請了一個空間存儲變量 i，但是它是常量階的移稳，跟數據規(guī)模 n 沒有關系蕴纳，所以我們可以忽略。第 3 行申請了一個大小為 n 的 int 類型數組个粱，除此之外古毛，剩下的代碼都沒有占用更多的空間，所以整段代碼的空間復雜度就是 O(n)都许。
我們常見的空間復雜度就是 O(1)稻薇、O(n)、O(n)胶征，像 O(logn)塞椎、O(nlogn) 這樣的對數階復雜度平時都用不到。而且睛低，空間復雜度分析比時間復雜度分析要簡單很多
時間復雜度
計算時間復雜度的3個方法
- 只關注循環(huán)或遞歸最多的一段代碼
- 加法法則：總復雜度等于量級最大的那段代碼的復雜度
- 乘法法則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積
(1).對于一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間
(2).對于順序結構,需要依次執(zhí)行一系列語句所用的時間可采用大O下"求和法則"
(3).對于選擇結構,如if語句,它的主要時間耗費是在執(zhí)行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間
(4).對于循環(huán)結構,循環(huán)語句的運行時間主要體現在多次迭代中執(zhí)行循環(huán)體以及檢驗循環(huán)條件的時間耗費,一般可用大O下"乘法法則"
(5)只需計算基本語句執(zhí)行次數的數量級案狠，只要保證基本語句執(zhí)行次數的函數中的最高次冪正確即可服傍，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化算法分析骂铁，并且使注意力集中在最重要的一點上：增長率吹零。
例1: O(1)
int cal(int n) {
int sum = 0; //1次頻度
int i = 1;//1次頻度
for (; i <= n; ++i) {//n次頻度
sum = sum + i;//n次頻度
}
return sum;
}
時間復雜度 T(n) = O(2n+2)=O(n)
例2: O( n )
int a=0; //1次頻度
int b=1; //1次頻度
for (i=1;i<=n;i++){ //n次頻度
s=a+b;//n次頻度
b=a; //n次頻度
a=s; //n次頻度
}
時間復雜度 T(n) = O(4+4n)=O(n)
例3: O( n^2 )
int cal(int n) {
int sum = 0;//1次頻度
int i = 1;//1次頻度
int j = 1;//1次頻度
for (; i <= n; ++i) {//n次頻度
j = 1;//n次頻度
for (; j <= n; ++j) {//n*n次頻度
sum = sum + i * j;//n*n次頻度
}
}
}
時間復雜度 T(n) = O(3+2n+2n*n)=O( n^2 )
例4: O( log^n )
for(i=0;i<n;){//f(n)次頻度
i*=2;//f(n)次頻度
}
假設語句2的頻度是f(n),則：2^f(n) <=n; f(n)<=log^n ; 取最大值f(n)=log^n ;T(n)=O(log^n )
例5:
當有若干個循環(huán)語句時，算法的時間復雜度是由嵌套層數最多的循環(huán)語句中最內層語句的頻度f(n)決定的从铲。
int x=1;
for(i=1;i<=n;i++) {
for(j=1;j<=i;j++){
for(k=1;k<=j;k++){
x++;
}
}
}
該程序段中頻度最大的語句是行號5瘪校，內循環(huán)的執(zhí)行次數雖然與問題規(guī)模n沒有直接關系，但是卻與外層循環(huán)的變量取值有關名段，而最外層循環(huán)的次數直接與n有關阱扬，因此可以從內層循環(huán)向外層分析語句(5)的執(zhí)行次數：
則該程序段的時間復雜度為T(n)=O(n3/6+低次項)=O(n3)
最好、最壞情況時間復雜度
// n 表示數組 array 的長度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
因為伸辟，要查找的變量 x 可能出現在數組的任意位置麻惶。如果數組中第一個元素正好是要查找的變量 x，那就不需要繼續(xù)遍歷剩下的 n-1 個數據了信夫，那時間復雜度就是 O(1)窃蹋。
但如果數組中不存在變量 x，那我們就需要把整個數組都遍歷一遍静稻，時間復雜度就成了 O(n)警没。所以，不同的情況下振湾，這段代碼的時間復雜度是不一樣的杀迹。
平均情況時間復雜度(加權平均時間復雜度 或 期望時間復雜度)
在數組的 0～n-1 位置中要查找的變量 x 在數組中的位置，有 n+1 種情況：不在數組中押搪。我們把每種情況下树酪，查找需要遍歷的元素個數累加起來，然后再除以 n+1大州，就可以得到需要遍歷的元素個數的平均值续语，即：
[圖片上傳失敗...(image-f1905f-1554175993123)]
前面的推導過程中存在的最大問題就是，沒有將各種情況發(fā)生的概率考慮進去厦画。如果我們把每種情況發(fā)生的概率也考慮進去疮茄，那平均時間復雜度的計算過程就變成了這樣：
[圖片上傳失敗...(image-976878-1554175993123)]
引入概率之后，前面那段代碼的加權平均值為 (3n+1)/4根暑。用大 O 表示法來表示娃豹，去掉系數和常量，這段代碼的加權平均時間復雜度仍然是 O(n)购裙。
均攤時間復雜度
// array 表示一個長度為 n 的數組
// 代碼中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
最理想的情況下，數組中有空閑空間鹃栽，我們只需要將數據插入到數組下標為 count 的位置就可以了躏率，所以最好情況時間復雜度為 O(1)躯畴。最壞的情況下，數組中沒有空閑空間了薇芝，我們需要先做一次數組的遍歷求和蓬抄，然后再將數據插入，所以最壞情況時間復雜度為 O(n)夯到。
假設數組的長度是 n嚷缭，根據數據插入的位置的不同，我們可以分為 n 種情況耍贾，每種情況的時間復雜度是 O(1)阅爽。除此之外，還有一種“額外”的情況荐开，就是在數組沒有空閑空間時插入一個數據付翁，這個時候的時間復雜度是 O(n)。而且晃听，這 n+1 種情況發(fā)生的概率一樣百侧，都是 1/(n+1)。所以能扒，根據加權平均的計算方法佣渴，我們求得的平均時間復雜度就是：平均時間復雜度是O(1)
[圖片上傳失敗...(image-2a5a12-1554175993123)]
我們還是繼續(xù)看在數組中插入數據的這個例子。每一次 O(n) 的插入操作初斑，都會跟著 n-1 次 O(1) 的插入操作辛润，所以把耗時多的那次操作均攤到接下來的 n-1 次耗時少的操作上，均攤下來越平，這一組連續(xù)的操作的均攤時間復雜度就是 O(1)
分析
// 全局變量频蛔，大小為 10 的數組 array，長度 len秦叛，下標 i晦溪。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往數組中添加一個元素
void add(int element) {
if (i >= len) { // 數組空間不夠了
// 重新申請一個 2 倍大小的數組空間
int new_array[] = new int[len*2];
// 把原來 array 數組中的數據依次 copy 到 new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array 復制給 array，array 現在大小就是 2 倍 len 了
array = new_array;
len = 2 * len;
}
// 將 element 放到下標為 i 的位置挣跋，下標 i 加一
array[i] = element;
++i;
}
1. 最好情況時間復雜度為 O(1)
2. 最壞情況分析：
最壞情況代碼執(zhí)行的次數跟每次數組的長度有關
第1次調用insert的執(zhí)行的次數為 n ,
第2次調用insert的執(zhí)行的次數為 2n ,
第3次調用insert的執(zhí)行的次數為 2^2 * n
第k次調用insert的執(zhí)行的次數為 2^(k-1) * n
最壞時間復雜度為 O(n)三圆。
3. 平均情況分析
當每次遇到最壞情況時數組會進行2倍擴容，原數組被導入新數組避咆，雖然數組的長度變大了舟肉，但是插入操作落在的區(qū)間的長度是一樣的，分別是0~len-1, len~(2len-1),....查库；
插入的情況仍是len+1種：0~len-1和插滿之后的O(len)路媚；所以每次插入的概率是：p= 1/len+1，
最后求出加權平均時間復雜度為 1*p + 2*p+ ??? + len*p + len * p = O(1) ;
4. 均攤時間復雜度 O(1)
而均攤復雜度由于每次O(len)的出現都跟著len次O(1)樊销，是前后連貫的整慎，因而將O(len)平攤到前l(fā)en次上脏款，得出平攤復雜度是O(1)
