什么是算法熟空？
算法是用于解決特定問(wèn)題的一系列的執(zhí)行步驟。
以下算法是為了解決兩數(shù)相加的問(wèn)題竟纳。
// 計(jì)算a和b的和
public static int plue(int a, int b){
return a + b;
}
以下算法是為了解決 n個(gè)數(shù)字的和 的問(wèn)題撵溃。
// 1+2+3+...+n
public static int sum(int n){
int result = 0;
for(int i = 1; i <= n; i++){
result += I;
}
return result;
}
使用不同算法，解決同一個(gè)問(wèn)題锥累，效率可能相差非常大缘挑。
比如：求第 n 個(gè)斐波那契數(shù)（fibonacci number）
如何評(píng)判一個(gè)算法的好壞？
如果單從執(zhí)行效率上進(jìn)行評(píng)估揩悄，可能會(huì)想到這么一種方案：
比較不同算法對(duì)同一組輸入的執(zhí)行處理時(shí)間
這種方案也叫做：事后統(tǒng)計(jì)法
上述方案有比較明顯的缺點(diǎn)：
執(zhí)行時(shí)間嚴(yán)重依賴(lài)硬件以及運(yùn)行時(shí)各種不確定的環(huán)境因素
必須編寫(xiě)相應(yīng)的測(cè)算代碼
測(cè)試數(shù)據(jù)的選擇比較難保證公正性
一般從以下維度來(lái)評(píng)估算法的優(yōu)劣：
正確性卖哎、可讀性、健壯性（對(duì)不合理輸入的反應(yīng)能力和處理能力）
時(shí)間復(fù)雜度（time complexity）
估算程序指令的執(zhí)行次數(shù)（執(zhí)行時(shí)間）
空間復(fù)雜度（space complexity）
估算所需占用的存儲(chǔ)空間
由于現(xiàn)在硬件發(fā)展的較好删性，一般情況下我們更側(cè)重于時(shí)間復(fù)雜度亏娜。
大O表示法（Big O）
一般用大O表示法來(lái)描述復(fù)雜度，它表示的是數(shù)據(jù)規(guī)模 n 對(duì)應(yīng)的復(fù)雜度蹬挺。
忽略常數(shù)维贺、系數(shù)、低階：
9 >> O(1)
2n + 3 >> O(n)
n2 + 2n + 6 >> O(n2)
4n3 + 3n2 + 22n + 100 >> O(n3)
寫(xiě)法上巴帮，n3 等價(jià)于 n^3
注意：大O表示法僅僅是一種粗略的分析模型溯泣，是一種估算，能幫助我們短時(shí)間內(nèi)了解一個(gè)算法的執(zhí)行效率榕茧。
對(duì)數(shù)階的細(xì)節(jié)
對(duì)數(shù)階一般省略底數(shù)
log29 ? log9n >> log2n
所以 O(log2n) 垃沦、O(log9n) 統(tǒng)稱(chēng)為 O(logn)
常見(jiàn)的復(fù)雜度
多個(gè)數(shù)據(jù)規(guī)模的情況
時(shí)間復(fù)雜度：O(n + k)
public static void test(int n, int k){
for(int i = 0; i < n; i++){
System.out.println("test");
}
for (int i = 0; i < k; i++){
System.out.println("test");
}
}
