數(shù)據(jù)結(jié)構(gòu)----效率問題

一.衡量效率

1.衡量效率的兩個維度

1.時間維度：時間復(fù)雜度：Time Complexity

時間復(fù)雜度是代碼總的運行次數(shù)（粗糙）

2.空間維度：空間復(fù)雜度：Space Complexity

空間復(fù)雜度是額外申請的空間

3.注意：

? 1.復(fù)雜度表示方法為 O()

2. 如果時間和空間不能同時達(dá)到一個理想狀態(tài)，時間優(yōu)先，用空間換時間 。一些特殊的應(yīng)用場合會用空間換時間

3. 一般算循環(huán)的時間復(fù)雜度，看循環(huán)體執(zhí)行幾次就可以

   也可以看代碼總執(zhí)行次數(shù)是看總共執(zhí)行了多少條語句

2.復(fù)雜度要求

1.多項級的運算結(jié)果，只保留最大項（最高次冪）

2.常系數(shù)省舍去

3.如果程序在有限棵樹的資源消耗內(nèi)即可完成(與n無關(guān))，那么復(fù)雜度為O(1)

3.看下面代碼判斷時間復(fù)雜度

//時間復(fù)雜度為 O(n)
for(int i=0;i<n;i++){cout<<i<<endl;
}//時間復(fù)雜度為 O(log2的n次方)
for(int i=1;i<=n;i*=2){cout<<i<<endl;
}//時間復(fù)雜度為 O(n的平方)
for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cout<<i<<"  "<<j<<endl;}
}//時間復(fù)雜度為 O(n的立方)
for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){for(int k=1;k<=j;k++){cout<<i<<"  "<<j<<endl;}}
}

6.關(guān)于復(fù)雜度計算的一些經(jīng)驗性結(jié)論

1.單純的順序和選擇結(jié)構(gòu)，時間復(fù)雜度為O(1)

2.一般的一層循環(huán)時間復(fù)雜度為O(n)

3.兩個并列的循環(huán)，時間復(fù)雜度max(O(m),O(n))

4.一般的兩層循環(huán)嵌套，時間復(fù)雜度是O(n的平方)

5.一般會選擇遞歸、分治、動態(tài)規(guī)劃等方法提升時間效率（空間換時間）