一、什么是O，時(shí)間復(fù)雜度
1剃法、概念
n表示數(shù)據(jù)規(guī)模
O(f(n)) 表示運(yùn)行算法所需要的執(zhí)行的指令數(shù)，和f(n) 成正比路鹰。
O(nlogn + n) = O(nlogn)
但贷洲，O(AlogA +B) 中AB不能互相替換，AB不是一個(gè)問題規(guī)模晋柱，如：鄰接表實(shí)現(xiàn)對(duì)圖的遍歷 O(V + E)幾個(gè)常用算法時(shí)間復(fù)雜度：
二分查找發(fā)O(logn) 所需執(zhí)行指令數(shù)：alogn
尋找數(shù)組中的最大/小值 O(n) 所需執(zhí)行指令數(shù)：bn
歸并排序酸法O(nlogn) 所需執(zhí)行指令數(shù)：cnlogn
選擇排序算法O(n^2) 所需執(zhí)行指令數(shù)：dn^2
二优构、數(shù)據(jù)規(guī)模n
1、數(shù)據(jù)規(guī)模：運(yùn)行時(shí)間
10^8：0.4秒
10^9：4秒
如果想要在1s內(nèi)解決問題：
- O(n^2) 的算法可以處理大約10^4級(jí)別的數(shù)據(jù)（一次操作）
- O(n) 的算法可以處理大約10^8級(jí)別的數(shù)據(jù)
- O(nlogn) 的算法可以處理大約10^7級(jí)別的數(shù)據(jù)
2雁竞、空間復(fù)雜度
- 多開一個(gè)輔助的數(shù)組：O(n)
- 多開一個(gè)輔助的二維數(shù)組：O(n^2)
- 多開常數(shù)空間：O(1)
- 遞歸調(diào)用是有空間代價(jià)的钦椭，遞歸的深度即是多的空間。
三碑诉、例子
1彪腔、例題
有一個(gè)字符串?dāng)?shù)組，將數(shù)組中的每一個(gè)字符串按照字母序排序进栽；之后在將整個(gè)字符串?dāng)?shù)組按照字典序排序德挣。整個(gè)操作的時(shí)間復(fù)雜度？
分析：
假設(shè)最長字符串長度S泪幌；數(shù)組中有n個(gè)字符串盲厌。
對(duì)每個(gè)字符串排序：O(slogs)
將字符串?dāng)?shù)組中n個(gè)字符串排序：O(snlogn)
整體：O(nslogs) + O(snlogn) = O(nslogs + snlogn) = O(ns*(logs+logn))
- 排序中比較的次數(shù)的復(fù)雜度為 O(nlogn)署照，即整型時(shí)排序的時(shí)間復(fù)雜度。
- 兩個(gè)字符串（長s）進(jìn)行比較吗浩，還需比較兩個(gè)字符串的字典序建芙，即需要時(shí)間復(fù)雜度 O(s)。
- 算法復(fù)雜度在有些情況是與用例相關(guān)的
2懂扼、二分查找法
3禁荸、int轉(zhuǎn)string——O(logn)
- O(logaN) = O(logbN) =O(logN) 底省略
4、注意循環(huán)條件——O(logn)
5阀湿、判斷是否是素?cái)?shù)——O(sqrt(n))
6赶熟、歸并排序——O(nlogn)
四、復(fù)雜度實(shí)驗(yàn)
通過讓數(shù)據(jù)規(guī)模n*2陷嘴，看時(shí)間增長趨勢(shì)
O(n^2)的話映砖，數(shù)據(jù)擴(kuò)大2倍，時(shí)間擴(kuò)大4倍灾挨。
五邑退、遞歸算法分析
- 不是有遞歸的函數(shù)就一定是O(nlogn)
1、遞歸中進(jìn)行一次遞歸調(diào)用
計(jì)算遞歸調(diào)用的深度劳澄，
2、多次遞歸調(diào)用
- 畫遞歸樹秒拔，數(shù)所有樹上的節(jié)點(diǎn)
- 2^(n+1) -1 = O(2^n) 指數(shù)級(jí)算法莫矗，非常慢
-
分治算法
歸并排序O(nlogn)
問題：為什么歸并排序不是O(2^n)砂缩，而是O(nlogn)作谚？
答：因?yàn)橹暗睦又姓脴涞纳疃葹閚，在排序搜索中樹的深度是logn梯轻；之前每個(gè)節(jié)點(diǎn)處理數(shù)據(jù)規(guī)模是一樣的食磕，排序搜索中處理每層數(shù)據(jù)規(guī)模是n，即n*logn喳挑。 - 主定理——?dú)w納了遞歸函數(shù)的時(shí)間復(fù)雜度彬伦。
六、均攤復(fù)雜度分析
1伊诵、動(dòng)態(tài)數(shù)組（Vector） 動(dòng)態(tài)棧单绑、動(dòng)態(tài)隊(duì)列
push_back時(shí)間復(fù)雜度：O(1)
2、避免復(fù)雜度震蕩
動(dòng)態(tài)數(shù)組實(shí)現(xiàn)：
public class MyVector<Item> {
private Item[] data;
private int size; // 存儲(chǔ)數(shù)組中的元素個(gè)數(shù)
private int capacity; // 存儲(chǔ)數(shù)組中可以容納的最大的元素個(gè)數(shù)
public MyVector(){
data = (Item[])new Object[100];
size = 0;
capacity = 100;
}
// 添加元素——平均復(fù)雜度為 O(1)
public void push_back(Item e){
if(size == capacity)
resize(2 * capacity);
data[size++] = e;
}
// 刪除元素曹宴，輸出pop出的元素ret——平均復(fù)雜度為 O(1)
// 并不是真正的刪除搂橙，通過調(diào)整size來動(dòng)態(tài)改變數(shù)組
public Item pop_back(){
if(size <= 0)
throw new IllegalArgumentException("can not pop back for empty vector.");
Item ret = data[size-1];
size --;
// 在size達(dá)到靜態(tài)數(shù)組最大容量的1/4時(shí)才進(jìn)行resize
// resize的容量是當(dāng)前最大容量的1/2
// 防止復(fù)雜度的震蕩
if(size == capacity / 4)
resize(capacity / 2);
return ret;
}
// 復(fù)雜度為 O(n)
private void resize(int newCapacity){
assert newCapacity >= size;
Item[] newData = (Item[])new Object[newCapacity];
// 把data中的元素，存到newData數(shù)組中
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
// 將修改容量后的數(shù)組賦給data
data = newData;
capacity = newCapacity;
}
// 注意：Java語言由于JVM內(nèi)部機(jī)制的因素笛坦，測量的性能時(shí)間有可能是跳躍不穩(wěn)定的区转。
public static void main(String[] args) {
for( int i = 10 ; i <= 26 ; i ++ ){
int n = (int)Math.pow(2,i);
long startTime = System.currentTimeMillis();
MyVector<Integer> vec = new MyVector<Integer>();
for(int num = 0 ; num < n ; num ++){
vec.push_back(num);
}
for(int num = 0 ; num < n ; num ++){
vec.pop_back();
}
long endTime = System.currentTimeMillis();
System.out.print(2 * n + " operations: \t");
System.out.println((endTime - startTime) + " ms");
}
}
}
ps：截圖代碼C++苔巨，代碼段java
