第一章： 基本概念（主要在選擇題）演算法的特性等
第二章： 漢諾塔（記演算法） 棋盤覆蓋（會過程） 快速排序（記演算法）
第三章： 0-1揹包問題
第四章： 最小生成樹（兩個）
第五章： 0-1揹包
第六章： 看：單源最短路徑問題、裝載問題
第九章：p類與np類問題，多項式時間複雜度
第一章：演算法概述
1、演算法的概念：演算法是指解決問題的一種方法或乙個過程。更嚴格地講，演算法是由若干條指令組成的有窮序列，且滿足下述4條性質:輸入、輸出、確定性、有限性。（有效性）
2、所需資源越多，該演算法的複雜性越高，反之。 演算法的複雜性：是演算法執行所需要的計算機資源的量。
3、三種情況考慮時間複雜性：最壞情況、最好情況、平均情況 。
實踐表明：可操作性最好且具有實際價值的是最壞情況下的時間複雜性。
4、複雜性漸近性態：上界：ο，下界：ω
上界ο：定義：如果存在大於0的常數c和自然數n0，使得當n≥n0時有f(n)≤cg(n)，則稱函式f(n)當n充分大時上有界，且g(n)是它的乙個上界，記為f(n)=ο(g(n))。
這時還說f(n)的階不高於g(n)的階。
意義：根據符號ο的定義，用它評估演算法的複雜性，得到的只是當規模充分大時的乙個上界。這個上界的階越低，則評估就越精確，結果就越有價值。
下界ω：定義：如果存在大於0的常數c和自然數n0，使得當n≥n0時有f(n) ≥cg(n)，則稱函式f(n)當n充分大時下有界，且g(n)是它的乙個下界，記為f(n)= ω(g(n))。
這時還說f(n)的階不低於g(n)的階。
優點：與ο的定義對稱； 缺點：當f(n)對自然數的不同無窮子集有不同的表示式，且有不同的階時，不能更好的刻畫出f(n)的下界。
意義：用ω評估演算法的複雜性，得到的只是該複雜性的乙個下界。這個下界的階越高，則評估就越精確，結果就越有價值。
5、各種漸近階的高低順序：
6、多項式時間演算法和指數時間演算法：
7、問題或某演算法的下界：
8、基於比較排序演算法的下界：
9、任何乙個演算法的設計取決於選定的邏輯結構；而演算法的最終實現依賴於採用的儲存結構。
10、樹的遍歷就是按某種次序訪問樹中的結點，要求每個結點訪問一次且僅訪問一次。
設訪問根結點記作 v 遍歷根的左子樹記作 l 遍歷根的右子樹記作 r
則可能的遍歷次序有
前序 vlr
中序 lvr
後序 lrv
習題1-3。
演算法的時間效率和空間效率都用輸入規模的函式進行度量
用演算法基本操作的執行次數來度量演算法的時間效率。通過計算演算法消耗的額外儲存單元的數量來度量空間效率
在輸入規模相同的情況下，有些演算法的效率會有顯著差異。對於這樣的演算法，需要區分最差效率，平均效率和最優效率
分析演算法的時間主要關心的是，當演算法的輸入規模增大時，其執行時間函式的增長次數
f(n): 乙個演算法的執行時間，常常用基本操作次數來表示。
g(n):乙個用來和該演算法基本操作次數作比較的函式。
ο(g(n))：增長次數小於等於g(n) (以及其常數倍，n趨向於無窮大)的函式集合。
不高於g(n)，上界為g(n)
ω(g(n))：增長次數大於等於g(n) (以及其常數倍，n趨向於無窮大)的函式集合。
第二章：遞迴與分治策略
1、遞迴演算法：直接或間接地呼叫自身的演算法。 遞迴函式：
用函式自身給出定義的函式。 每個遞迴函式必須有非遞迴定義的初始值。 邊界條件與遞迴方程是遞迴函式的二個要素，遞迴函式只有具備了這兩個要素，才能在有限次計算後得出結果。
型別：階乘函式、fibonacci數列、ackerman函式 、排列問題、整數劃分問題、hanoi塔問題 。
優點：結構清晰，可讀性強，而且容易用數學歸納法來證明演算法的正確性，因此它為設計演算法、除錯程式帶來很大方便。
缺點：遞迴演算法的執行效率較低，無論是耗費的計算時間還是占用的儲存空間都比非遞迴演算法要多。
2、hanoi塔問題 （遞迴演算法）：
void hanoi(int n, int a, int b, int c)
}3、分治法的基本思想：將乙個規模為n的問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞迴地解這些子問題，然後將各子問題的解合併得到原問題的解。
適用條件：分治法所能解決的問題一般具有以下幾個特徵：
● 該問題的規模縮小到一定的程度就可以容易地解決；
● 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質
● 利用該問題分解出的子問題的解可以合併為該問題的解；
● 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。
這條特徵涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重複地解公共的子問題，此時雖然也可用分治法，但一般用動態規劃較好。
基本步驟：
divide-and-conquer(p)
一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
複雜性分析：
乙個分治法將規模為n的問題分成k個規模為n／m的子問題去解。設分解閥值n0=1，且adhoc解規模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合併為原問題的解需用f(n)個單位時間。
用t(n)表示該分治法解規模為|p|=n的問題所需的計算時間，則有：
4、棋盤覆蓋（過程）
問題描述：在乙個2k×2k 個方格組成的棋盤中，恰有乙個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態的l型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個l型骨牌不得重疊覆蓋。
過程：用分治策略。當k>0時，將2k×2k棋盤分割為4個2k-1×2k-1 子棋盤(a)所示。
特殊方格必位於4個較小子棋盤之一中，其餘3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉化為特殊棋盤，可以用乙個l型骨牌覆蓋這3個較小棋盤的會合處，如 (b)所示，從而將原問題轉化為4個較小規模的棋盤覆蓋問題。遞迴地使用這種分割，直至棋盤簡化為棋盤1×1。
5、快速排序（演算法）（不一定考）
template
void quicksort (type a, int p, int r)
template
int partition (type a, int p, int r)
快速排序演算法的效能取決於劃分的對稱性。
第三章：動態規劃
1、動態規劃：自底向上的方法，小規模到大規模
備忘錄：自頂向下的，由大規模到小規模。
適用條件：一般來說，當乙個問題的所有子問題都至少要解一次時，用動態規劃演算法比用備忘錄方法好。此時，動態規劃演算法沒有任何多餘的計算，還可以利用其規則的**訪問方式來減少在動態規劃演算法中的計算時間和空間需求。
當子問題空間中部分子問題可以不必求解時，易用備忘錄方法則較為有利，因為從其控制結構可以看出，該方法只解那些確實需要求解的子問題。
2、基本思想：也是將待求解問題分解成若干個子問題i，先求解子問題，然後從這些子問題的解得到原問題的解。
與分治法不同的是，適合於動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的。
可以用乙個表來記錄所有已解決的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。
3、動態規劃方法是一種對具有交疊子問題的問題進行求解的技術。
動態規劃法是在每一決策步上，列出各解可能的區域性解。按某些條件，捨棄那些肯定不能得到最優解的區域性解，這就是「最優性原理」
適用於解最優化問題。
4、和貪心法一樣，動態規劃也視問題求解為一多階段決策問題;動態規劃也不回溯。
雜訊複習提綱
第一章1.聽力損失 指某耳在乙個或幾個頻率的聽閾比正常耳的聽閾高出的分貝值 db 2.聲學系統的三個環節 聲源 傳播途徑 接收器。第二章1.聲能量 e 聲波傳播到靜止介質時，一方面使介質在平衡位置作往復振動，獲得振動動能 另一方面使介質產生膨脹和壓縮的疏密過程，介質獲得形變勢能，這兩部分能量的總和稱...
力學複習提綱
一 參照物 1 定義 為研究物體的運動假定的物體叫做參照物。3 選擇不同的參照物來觀察同乙個物體結論可能不同。同乙個物體是運動還是靜止取決於 這就是運動和靜止的 4 不能選擇所研究的物件本身作為參照物那樣研究物件總是靜止的。練習1 一輛汽車在平直的公路上向東快速行駛，乙個人在該公路的便道上向東散步，...
生理複習提綱
一 概念 興奮性閾刺激內環境穩態 1.物質的跨膜轉運有哪幾種形式？2.機體功能的調節有幾種方式？各有何特點？3.闡述細胞靜息電位 動作電位產生的機制。包括恢復過程 一 概念 滲透脆性溶血血液凝固 血型紅細胞凝集 二 問答題 1.血漿蛋白具有哪些生理機能？2.紅細胞數量的穩定是怎樣維持的?3.紅細胞的...