一藕坯、算法定義：
對(duì)特定問題糾結(jié)步驟的一種描述团南；它是指令的有限序列噪沙，其中每條指令表示一個(gè)或多個(gè)操作
二、5個(gè)重要特性：
- 有窮性
一個(gè)算法必須總是（對(duì)任何合法的輸入）在執(zhí)行有窮步后結(jié)束吐根，且每步都可以在有窮時(shí)間內(nèi)完成正歼。
- 確定性
算法中的每條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性拷橘。并且在任何條件下局义，算法只有唯一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出冗疮。
- 可行性
一個(gè)算法是能行的萄唇，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次實(shí)現(xiàn)。
- 輸入
一個(gè)算法有零個(gè)或多個(gè)輸入术幔，這些輸入取自某個(gè)特定的對(duì)象的集合另萤。
- 輸出
一個(gè)算法有一個(gè)或多個(gè)的輸出，這些輸出是同輸入有著特定的關(guān)系的量诅挑。
11.png
三四敞、算法設(shè)計(jì)的要求
1、正確性
算法應(yīng)當(dāng)滿足具體問題的需求,能夠通過特定的問題測(cè)試拔妥。
2忿危、可讀性
算法主要是為了人的閱讀與交流，其次才是機(jī)器的執(zhí)行
3没龙、健壯性
當(dāng)輸入非法的數(shù)據(jù)時(shí)癌蚁，算法也能狗適當(dāng)做出反應(yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名奇妙的輸出結(jié)果
4兜畸、效率與低存儲(chǔ)量需求
效率指算法運(yùn)行的時(shí)間，執(zhí)行時(shí)間短效率高碘梢；存儲(chǔ)量需求是指算法執(zhí)行過程中所需的最大存儲(chǔ)空間咬摇。
二者都與問題的規(guī)模相關(guān)，同時(shí)也要根據(jù)實(shí)際需求決擇煞躬，要效率肛鹏，還是要節(jié)省空間，或者折中恩沛。一般情況二者不可得兼在扰，要么用空間換時(shí)間，要么用時(shí)間換空間雷客。
四芒珠、算法的好壞評(píng)定標(biāo)準(zhǔn)
時(shí)間復(fù)雜度 ：T(n)
根據(jù)算法寫成的程序在執(zhí)行時(shí) 耗費(fèi)時(shí)間的長度。這個(gè)長度往往也與輸入數(shù)據(jù)的規(guī) 模有關(guān)搅裙。時(shí)間復(fù)雜度過高的低效算法可能導(dǎo)致我們 在有生之年都等不到運(yùn)行結(jié)果皱卓。
空間復(fù)雜度 ：S(n)
根據(jù)算法寫成的程序在執(zhí)行時(shí) 占用存儲(chǔ)單元的長度裹芝。這個(gè)長度往往與輸入數(shù)據(jù)的 規(guī)模有關(guān)∧戎空間復(fù)雜度過高的算法可能導(dǎo)致使用的 內(nèi)存超限嫂易，造成程序非正常中斷。
耗費(fèi)空間的的算法實(shí)例：
使用遞歸調(diào)用打印N個(gè)連續(xù)的數(shù)字：由于遞歸會(huì)不斷存儲(chǔ)上一個(gè)函數(shù)的狀態(tài)與地址等信息掐禁，會(huì)不斷地申請(qǐng)空間怜械，可能會(huì)將空間占滿
耗費(fèi)時(shí)間的算法實(shí)例：
在求多項(xiàng)式的算法設(shè)計(jì)中，直接的按照公式的設(shè)計(jì)的算法由于引入了大量的冪次運(yùn)算傅事，增加了計(jì)算機(jī)的運(yùn)算量(計(jì)算機(jī)更加愿意做加減法運(yùn)算)缕允，改進(jìn)算法利用提取公因式的方式（秦九韶公式），大大減少了乘法運(yùn)算
五享完、分析算法好壞：主要關(guān)心最壞情況復(fù)雜度灼芭，其次關(guān)心平均復(fù)雜度
最好情況、最壞情況 和 平均情況
- 某個(gè)特定的數(shù)據(jù)集能讓算法的執(zhí)行情況極好般又，這就是最「最好情況」
- 而另一個(gè)不同的數(shù)據(jù)會(huì)讓算法的執(zhí)行情況變得極差彼绷，這就是「最壞情況」
- 不過在大多數(shù)情況下，算法的執(zhí)行情況都介于這兩種極端情況之間茴迁，也就是「平均情況」
因此要理解好不同情況之間的差別寄悯，不要被極端情況迷惑。
- 「最優(yōu)情況」:沒有什么大的價(jià)值堕义，因?yàn)樗鼪]有提供什么有用信息猜旬，反應(yīng)的只是最樂觀最理想的情況，沒有參考價(jià)值倦卖。
- 「平均情況」:是對(duì)算法的一個(gè)全面評(píng)價(jià)洒擦，因?yàn)樗暾娴姆从沉诉@個(gè)算法的性質(zhì)，但從另一方面來說怕膛，這種衡量并沒有什么保證熟嫩，并不是每個(gè)運(yùn)算都能在這種情況內(nèi)完成。
- 「最壞情況」:它提供了一種保證褐捻，這個(gè)保證運(yùn)行時(shí)間將不會(huì)再壞了掸茅，所以一般我們所算的時(shí)間復(fù)雜度是最壞情況下的時(shí)間復(fù)雜度，做事要考慮到最壞的情況是一個(gè)道理柠逞。
常見數(shù)量級(jí)函數(shù)
注：
平常設(shè)計(jì)算法過程中昧狮，養(yǎng)成分析算法復(fù)雜度的習(xí)慣，看看是否能夠優(yōu)化板壮，比如設(shè)計(jì)了一個(gè)n^2 的算法逗鸣，應(yīng)立刻想到能否優(yōu)化到 nlogn 的數(shù)量級(jí)。
如何分析算法的復(fù)雜度：
推薦文章——循序漸進(jìn)帶你學(xué)習(xí)時(shí)間復(fù)雜度和空間復(fù)雜度
