1. 偽代碼

1.1與真碼的區(qū)別：

1. 偽代碼與真碼的區(qū)別在于，在偽代碼中，我們使用最清晰、最簡(jiǎn)潔的表示方法來(lái)說(shuō)明給定的算法。有時(shí)最清晰的表示方法時(shí)英語(yǔ)，所以如果你遇到一個(gè)英文短語(yǔ)或句子嵌入在一段真碼中就不要吃驚。
2. 偽代碼與真碼的另一個(gè)區(qū)別是偽代碼通常不關(guān)心軟件工程的問(wèn)題。
3. 偽代碼為了更簡(jiǎn)潔的表達(dá)算法的本質(zhì)，常常忽略數(shù)據(jù)抽象、模塊性和錯(cuò)誤處理的問(wèn)題。

1.2 偽代碼中的約定：

1. 縮進(jìn)表示快結(jié)構(gòu)
2. while、for與repeat-until等循環(huán)結(jié)構(gòu)以及if-else等條件結(jié)構(gòu)與c、c++、python和pascal中的結(jié)構(gòu)具有類(lèi)似的解釋。當(dāng)一個(gè)for循環(huán)每次迭代增加其循環(huán)計(jì)數(shù)器時(shí)，我們使用關(guān)鍵詞to，當(dāng)一個(gè)for循環(huán)每次迭代減少其循環(huán)計(jì)數(shù)器時(shí)，我們使用關(guān)鍵詞downto。當(dāng)循環(huán)計(jì)數(shù)器以大于1的一個(gè)量改變時(shí)，該改變量跟在可選關(guān)鍵詞by之后。
3. 符號(hào)“//”表示該行后面部分是注釋
4. 多重賦值i=j=e是將表達(dá)式e的值賦給變量i和j；
5. 變量（如i，j和key等）是局部于給定過(guò)程的。在沒(méi)有顯示說(shuō)明的情況下，我們不使用全局變量
6. 數(shù)組元素是通過(guò)“數(shù)組名[下標(biāo)]”這樣的形式來(lái)進(jìn)行訪(fǎng)問(wèn)的。A[i]表示數(shù)組A的第i個(gè)元素，符號(hào)“..”用來(lái)表示數(shù)組中的一個(gè)取值范圍；
7. 復(fù)合數(shù)據(jù)一般組織成對(duì)象，它們是由屬性（attribute）或域（field）所組成的。域的訪(fǎng)問(wèn)是由域名跟由方括號(hào)的對(duì)象名形式來(lái)表示。在表示數(shù)組元素和對(duì)象屬性時(shí)，都要用到方括，一般來(lái)說(shuō)，通過(guò)上下文就可以看出其含義；
   用于表示一個(gè)數(shù)組或?qū)ο蟮淖兞勘豢醋魇侵赶虮硎緮?shù)組或?qū)ο蟮臄?shù)據(jù)的一個(gè)指針。對(duì)于某個(gè)對(duì)象x的所有域f，賦值y=x就使得f[y] = f[x]。更進(jìn)一步，如果有f[x] = 3，則不僅有f[x] = 3，同時(shí)f[y] = 3。換言之，在賦值 y = x 后，x 和 y 指向同一個(gè)對(duì)象；
   有時(shí)，一個(gè)指針不指向任何對(duì)象。這使，我們賦給它NULL；
8. 參數(shù)采用按值傳遞方式：被調(diào)用的過(guò)程會(huì)收到參數(shù)的的一份副本。如果它對(duì)某個(gè)參數(shù)賦值的話(huà)，主調(diào)過(guò)程是看不見(jiàn)這一變動(dòng)的。當(dāng)對(duì)象被傳遞時(shí)，實(shí)際傳遞的是一個(gè)指向?qū)ο髷?shù)據(jù)的指針，而對(duì)象的各個(gè)域則不被拷貝；
9. 布爾運(yùn)算符“and”和“or”都具有短路能力。亦即，當(dāng)我們求表達(dá)式“x and y”的值時(shí)，首先計(jì)算x的值。如果x的值為FALSE，那么整個(gè)表達(dá)式的值就不可能為T(mén)RUE了，因而就無(wú)需再對(duì)y求值了。但是，如果x的值為T(mén)RUE的話(huà)，就必須進(jìn)一步計(jì)算出y的值，才能確定整個(gè)表達(dá)式的值。類(lèi)似地，在計(jì)算表達(dá)式“x or y”的值時(shí)，僅當(dāng)x的值為FALSE時(shí)，才需要計(jì)算子表達(dá)式y(tǒng)的值。短路運(yùn)算符允許我們寫(xiě)出如“x=/(不等于)NIL and f[x] = y“這樣的布爾表達(dá)式，而不用擔(dān)心當(dāng)我們?cè)噲D在x為NIL時(shí)計(jì)算f[x]，會(huì)發(fā)生怎樣的情況。

2. 循環(huán)不變式

循環(huán)不變式主要用來(lái)幫助我們理解算法的正確性，關(guān)于循環(huán)不變式，我們必須證明三條性質(zhì)
1.初始化：循環(huán)的第一次迭代之前，它為真
2.保持：如果循環(huán)的某次迭代之前它為真，那么下次迭代之前它仍為真
3.終止：在循環(huán)終止時(shí)，不變式為我們提供一個(gè)有用的性質(zhì)，該性質(zhì)有助與證明算法是正確的
注意：
1.當(dāng)前兩條性質(zhì)成立時(shí)，在循環(huán)的每次迭代之前循環(huán)不變式為真。(當(dāng)然，為了證明循環(huán)不變式在每次迭代之前保持為真，我們完全可以使用不同于循環(huán)不變式本身的其他已證實(shí)的事實(shí))注意，這類(lèi)似與數(shù)學(xué)歸納法，其中為了證明某條性質(zhì)成立，需要證明一個(gè)基本情況和一個(gè)歸納步。這里，證明第一次迭代之前不變式成立對(duì)應(yīng)于基本情況，證明從一次迭代到下一次迭代不變式成立對(duì)應(yīng)于歸納步。
2.第三條性質(zhì)是最重要的，因?yàn)槲覀儗⑹褂醚h(huán)不變式來(lái)證明正確性。通常我們和導(dǎo)致循環(huán)終止的條件一起使用循環(huán)不變式。終止性不同于我們通常使用數(shù)學(xué)歸納法的做法，在歸納法中，歸納步是無(wú)限使用的，這里當(dāng)循環(huán)終止時(shí)，停止“歸納”。

3. 循環(huán)不變式例子--插入排序

3.1 偽代碼:

參數(shù)是數(shù)組A[1...n]

INSERTION-SORT(A)
1  for j = 2 to A.length
2    key = A[j]
3    //insert A[j] into the sorted sequence A[1 ... j-1]
4   i  = j -1
5    while(i > 0 and A[i] > key)
6      A[i+1] = A[i]
7     i = i - 1
8    A[i + 1] = key

在for循環(huán)(循環(huán)變量為j)的每次迭代的開(kāi)始，包含元素A[1...j-1]的子數(shù)組構(gòu)成了當(dāng)前排序好的牌，剩余的子數(shù)組A[j+1...n]對(duì)應(yīng)于仍在桌子上的牌堆，我們把A[1...j-1]的這些性質(zhì)形式地表示為一個(gè)循環(huán)不變式:

3.2 解析

初始化：

首先證明在第一次循環(huán)迭代之前(當(dāng)j=2時(shí))，循環(huán)不變式成立。所以子數(shù)組A[1...j-1]僅由單個(gè)元素A[1]組成，實(shí)際上就是A[1]中原來(lái)的元素。而且該子數(shù)組是排序好的，這表明第一次循環(huán)跌打之前循環(huán)不變式成立

保持

"證明每次迭代保持循環(huán)不變式"
非形式化地，for循環(huán)體的第4-7行將A[j-1]、A[j-2]、A[j-3]等向右移動(dòng)一個(gè)位置，直到找到A[j]的適當(dāng)位置，第8行將A[j]的值插入該位置。這時(shí)子數(shù)組由原來(lái)在A[1...j]中的元素組成，但已按序排列

終止

導(dǎo)致for循環(huán)終止的條件是j>A.length=n,因?yàn)槊看蔚鷍+1，那么必有j = n+1，在循環(huán)不變式中將j用n+1代替，我們有：子數(shù)組A[1...n]由原來(lái)在A[1...n]中的元素組成，但已按需排列，這時(shí)，子數(shù)組就是整個(gè)數(shù)組，因此算法正確

4. 漸近記號(hào)

原文：https://blog.csdn.net/so_geili/article/details/53353593

4.1漸近精確界記號(hào)：Θ（big-theta）

Θ 的數(shù)學(xué)含義
方式一：設(shè)f(n)和g(n)是定義域?yàn)樽匀粩?shù)集合的函數(shù)。如果limn→∞f(n)g(n)存在，并且等于某個(gè)常數(shù)c(c>0)，那么f(n)=Θ(g(n)。通俗理解為f(n)和g(n)同階，ΘΘ用來(lái)表示算法的精確階。
方式二：Θ(g(n))={f(n):存在正常量c1、c2和n0，使得對(duì)所有n≥n00，有0≤c1g(n)≤f(n)≤c2g(n)}若存在正常量c1、c2，使得對(duì)于足夠大的n，函數(shù)f(n)能“夾入”c1g(n)與c2g(n)之間，則f(n)屬于集合Θ(g(n))，記作f(n)∈Θ(g(n))。作為代替，我們通常記“f(n)=Θ(g(n))”。

4.2 漸近上界記號(hào)：O(big-oh)

定義：設(shè)f(n)和g(n)是定義域?yàn)樽匀粩?shù)集N上的函數(shù)。若存在正數(shù)c和n0，使得對(duì)一切n≥n0n≥n0都有0≤f(n)≤cg(n)成立，則稱(chēng)f(n)的漸進(jìn)的上界是g(n)，記作f(n)=O(g(n))。通俗的說(shuō)n滿(mǎn)足一定條件范圍內(nèi)，函數(shù)f(n)的階不高于函數(shù)g(n)。

4.3 漸近下界記號(hào)：Ω(big-omege)

定義：設(shè)f(n)和g(n是定義域?yàn)樽匀粩?shù)集N上的函數(shù)。若存在正數(shù)c和n0，使得對(duì)一切n≥n0n≥n0都有0≤cg(n)≤f(n)成立，則稱(chēng)f(n)的漸進(jìn)的下界是g(n)，記作f(n)=Ω(g(n))。通俗的說(shuō)n滿(mǎn)足一定條件范圍內(nèi)，函數(shù)f(n)的階不低于函數(shù)g(n)。

4.4 非漸近緊確上界：o(小-oh)

定義1：設(shè)f(n)和g(n)和g(n)是定義域?yàn)樽匀粩?shù)集N上的函數(shù)。若對(duì)于任意正數(shù)c，都存在n0，使得對(duì)一切n≥n0都有0≤f(n)<cg(n)成立，則稱(chēng)f(n)的漸進(jìn)的非緊確上界是g(n)，記作f(n)=o(g(n))。通俗的說(shuō)n滿(mǎn)足一定條件范圍內(nèi)，函數(shù)f(n)f的階低于函數(shù)g(n)。
定義2：設(shè)f(n)和g(n))是定義域?yàn)樽匀粩?shù)集合的函數(shù)。如果limn→∞f(n)/g(n)=0，那么f(n)=o(g(n))。通俗理解為f(n)低于g(n)的階。

4.5 非漸近緊確下界：ω(小-omege)

定義1：設(shè)f(n)和g(n)和g(n)是定義域?yàn)樽匀粩?shù)集N上的函數(shù)。若對(duì)于任意正數(shù)c， 都存在n0，使得對(duì)一切n≥n0n≥n0都有0≤cg(n)<f(n)成立，則稱(chēng)f(n)f(n)的漸進(jìn)的非緊確下界是g(n)，記作f(n)=ω(g(n)。通俗的說(shuō)n滿(mǎn)足一定條件范圍內(nèi)，函數(shù)f(n)的階高于函數(shù)g(n)。
定義2：設(shè)f(n)和g(n)是定義域?yàn)樽匀粩?shù)集合的函數(shù)。如果limn→∞f(n)/g(n)=∞，那么f(n)=o(g(n))。通俗理解為f(n)高于g(n)的階。

4.6 漸近記號(hào)Θ、Ο、o、Ω、ω關(guān)系

關(guān)系