- 算法五個(gè)重要特征：
- 有窮性：保證執(zhí)行有限步驟之后結(jié)束祥楣；
- 確切性：每一步驟都有確切的定義开财；
- 輸入：每個(gè)算法有零個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況误褪，所謂零個(gè)輸入是指算法本身定除了初始條件责鳍；
- 輸出：每個(gè)算法有一個(gè)或多個(gè)輸出，顯示對(duì)輸入數(shù)據(jù)加工后的結(jié)果兽间。沒(méi)有輸出的算法是毫無(wú)意義的历葛；
- 可行性：在原則上算法能夠精確地運(yùn)行，進(jìn)行有限次運(yùn)算后即可完成一種運(yùn)算渡八。
常用基本算法：
快排 堆排序 歸排序 二分查找 線性查找 廣度優(yōu)先 深度優(yōu)先 動(dòng)態(tài)規(guī)劃常見(jiàn)算法思想：
枚舉 遞推 遞歸 分治 貪心 迭代時(shí)間復(fù)雜度和空間復(fù)雜度:
時(shí)間頻度 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間啃洋，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道屎鳍。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試宏娄，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了逮壁。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例孵坚，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度卖宠。記為T(n)巍杈。
時(shí)間復(fù)雜度 在剛才提到的時(shí)間頻度中，n稱為問(wèn)題的規(guī)模扛伍，當(dāng)n不斷變化時(shí)筷畦，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律刺洒。為此鳖宾，我們引入時(shí)間復(fù)雜度概念。 一般情況下逆航，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)鼎文，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)因俐，T（n)/f(n)的極限值為不等于零的常數(shù)拇惋，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度抹剩，簡(jiǎn)稱時(shí)間復(fù)雜度撑帖。
時(shí)間復(fù)雜度(從小到大)
常數(shù)階<對(duì)數(shù)階<線性階<線性對(duì)數(shù)階<平方階<立方階<K次方<指數(shù)階
優(yōu)先多項(xiàng)式，指數(shù)容易爆炸吧兔。順序結(jié)構(gòu)可以求和磷仰，取max，循環(huán)結(jié)構(gòu)用乘法境蔼。復(fù)雜結(jié)構(gòu)可分灶平，然后去低階、去常數(shù)箍土、去高階常參逢享。
空間復(fù)雜度
一個(gè)程序的空間復(fù)雜度是指運(yùn)行完一個(gè)程序所需內(nèi)存的大小。利用程序的空間復(fù)雜度吴藻，可以對(duì)程序的運(yùn)行所需要的內(nèi)存多少有個(gè)預(yù)先估計(jì)瞒爬。一個(gè)程序執(zhí)行時(shí)除了需要存儲(chǔ)空間和存儲(chǔ)本身所使用的指令、常數(shù)沟堡、變量和輸入數(shù)據(jù)外侧但，還需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為現(xiàn)實(shí)計(jì)算所需信息的輔助空間。程序執(zhí)行時(shí)所需存儲(chǔ)空間包括以下兩部分航罗≠骱幔
（1）固定部分。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個(gè)數(shù)多少粥血、數(shù)值無(wú)關(guān)柏锄。主要包括指令空間（即代碼空間）酿箭、數(shù)據(jù)空間（常量、簡(jiǎn)單變量）等所占的空間趾娃。這部分屬于靜態(tài)空間缭嫡。
（2）可變空間，這部分空間的主要包括動(dòng)態(tài)分配的空間抬闷，以及遞歸棧所需的空間等妇蛀。這部分的空間大小與算法有關(guān)。
一個(gè)算法所需的存儲(chǔ)空間用f(n)表示饶氏。S(n)=O(f(n)) 其中n為問(wèn)題的規(guī)模讥耗，S(n)表示空間復(fù)雜度。
- 常見(jiàn)數(shù)據(jù)結(jié)構(gòu)
數(shù)組 隊(duì)列 堆 棧 鏈表 樹 圖 散列表
- 四大結(jié)構(gòu)：集合結(jié)構(gòu) 線性結(jié)構(gòu) 圖形結(jié)構(gòu) 樹形結(jié)構(gòu)
- 數(shù)據(jù)類型：在C語(yǔ)言中疹启，數(shù)據(jù)類型可以分為：
原子類型：不可以再分解的基本類型，例如整型蔼卡、浮點(diǎn)型喊崖、字符型等。
結(jié)構(gòu)類型：由若干個(gè)類型組合而成雇逞，是可以再分解的荤懂，例如整型數(shù)組是由若干整型數(shù)據(jù)組成的。 - 兩種存儲(chǔ)方式：順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)
- 棧：一端 先進(jìn)后出 常見(jiàn)操作：push pop peek length clear
- 隊(duì)列：兩端 后進(jìn)先出
- 圖：有向 無(wú)序 簡(jiǎn)單 兩個(gè)數(shù)據(jù):頂點(diǎn)塘砸、表明是否訪問(wèn)的哈希值
- 二叉樹的特點(diǎn)：
每個(gè)結(jié)點(diǎn)最多有兩棵子樹节仿，所以二叉樹中不存在度大于2的結(jié)點(diǎn)。二叉樹中每一個(gè)節(jié)點(diǎn)都是一個(gè)對(duì)象掉蔬，每一個(gè)數(shù)據(jù)節(jié)點(diǎn)都有三個(gè)指針廊宪，分別是指向父母、左孩子和右孩子的指針女轿。每一個(gè)節(jié)點(diǎn)都是通過(guò)指針相互連接的箭启。相連指針的關(guān)系都是父子關(guān)系。 - 二叉樹的五種基本形態(tài)：
空二叉樹
只有一個(gè)根結(jié)點(diǎn)
根結(jié)點(diǎn)只有左子樹
根結(jié)點(diǎn)只有右子樹
根結(jié)點(diǎn)既有左子樹又有右子樹
