"磨棱角，褪優(yōu)越，沉下心"
"不止于心動(dòng)，更付諸于行動(dòng)，執(zhí)行力！“

引言

本章接著前面的緒論記錄，本章主要記錄算法相關(guān)的基本概念。在這里只記錄一些核心需要掌握的東西了。

算法與算法分析

算法定義

算法是對(duì)特定問題求解方法和步驟的一種描述，它是指令的有限序列。其中每個(gè)指令表示一個(gè)或多個(gè)操作。算法就是解決問題的方法和步驟。

算法的特性

• （1）有窮性
  一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。
• （2）確定性
  算法中的每一條指令必須有確切的含義，沒有二義性，在任何條件下，只有唯一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得到相同的輸出。
• （3）可行性
  算法是可執(zhí)行的，算法描述的操作可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)。
• （4）輸入
  一個(gè)算法有零個(gè)或多個(gè)輸入。
• （5）輸出
  一個(gè)算法有一個(gè)或多個(gè)輸出。

算法設(shè)計(jì)的要求

• （1）正確性（Correctness）
  正確性：算法滿足問題要求，能正確解決問題。
  算法轉(zhuǎn)化為程序后要注意：
  ①不含語法錯(cuò)誤。
  ②對(duì)于幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。
  ③對(duì)于精心選擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。
  ④對(duì)于一切合法的輸入數(shù)據(jù)都能得到滿足要求的結(jié)果。
  以第三層意義上的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。
• （2）可讀性（Readability）
  可讀性：
  ①算法應(yīng)該易于人的理解。
  ②晦澀難懂的算法易于隱藏較多錯(cuò)誤而難以調(diào)試。
• （3）健壯性（Robustness）（魯棒性）
  健壯性：
  ①指當(dāng)輸入非法數(shù)據(jù)時(shí)，算法恰當(dāng)?shù)淖龀龇磻?yīng)或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名其妙的輸出結(jié)果。
  ②處理出錯(cuò)的方法，不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。
• （4）高效性（Efficiency）
  高效性：要求花費(fèi)盡量少的時(shí)間和盡量低的存儲(chǔ)需求。

算法分析與評(píng)估

對(duì)于同一個(gè)問題，可能有許多種不同的方法，也就是有許多種算法，需要衡量評(píng)估哪種方法好，擇優(yōu)問題。

算法效率

算法效率以下兩個(gè)方面來考慮：

• 時(shí)間效率：指的是算法所耗費(fèi)的時(shí)間。
• 空間效率：指的是算法執(zhí)行過程中所耗費(fèi)的存儲(chǔ)空間。
  時(shí)間效率和空間效率有時(shí)候是矛盾的。

算法時(shí)間效率的度量

算法時(shí)間效率可以用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來度量。

（1）度量方法

• 事后統(tǒng)計(jì)：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開銷。
  缺點(diǎn)：編寫程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力；實(shí)驗(yàn)結(jié)果依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素，掩蓋算法本身的優(yōu)劣。
• 事前分析：對(duì)算法所消耗資源的一種估算方法。

事前分析方法：

方法：算法運(yùn)行時(shí)間=一個(gè)簡(jiǎn)單操作所需的時(shí)間*簡(jiǎn)單操作次數(shù)。

算法運(yùn)行時(shí)間=Σ每條語句的執(zhí)行次數(shù)*該語句執(zhí)行一次所需的時(shí)間。

每條語句的執(zhí)行次數(shù)又稱為語句頻度

算法運(yùn)行時(shí)間=Σ每條語句頻度*該語句執(zhí)行一次所需的時(shí)間

實(shí)際評(píng)估算法時(shí)間效率，并不需要很明確知道每條語句執(zhí)行的時(shí)間，這里運(yùn)用高數(shù)上面的極限、等價(jià)相關(guān)的思想，直接簡(jiǎn)化只用執(zhí)行的次數(shù)來衡量算法的時(shí)間效率了。
下面是資料的相關(guān)描述：
每條語句執(zhí)行一次所需的時(shí)間，一般是隨機(jī)器而異的。取決于機(jī)器的指令性能、速度以及編譯的代碼質(zhì)量。是由機(jī)器本身軟硬件環(huán)境決定的，它與算法無關(guān)。所以，我們可假設(shè)執(zhí)行每條語句所需的時(shí)間均為單位時(shí)間。此時(shí)對(duì)算法的運(yùn)行時(shí)間的討論就可轉(zhuǎn)化為討論該算法中所有語句的執(zhí)行次數(shù)，即頻度之和了。這就可以獨(dú)立于不同機(jī)器的軟硬件環(huán)境來分析算法的時(shí)間性能了。

例子：
兩個(gè)n*n矩陣相乘的算法

//兩個(gè)n*n矩陣相乘的算法
for(i = 1; i <= n; i++){//n+1次 
    for(j = 1; j <= n; j++){//n(n+1)次 
        c[i][j] = 0;//n*n次 
        for(k = 0; k < n; k++){//n*n*(n+1)次 
            c[i][j] = c[i][j] + a[i][k] * b[k][j];//n*n*n次 
        }
    }
}

時(shí)間復(fù)雜度

背景：

若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)= O(f(n))，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度（O是數(shù)量級(jí)的符號(hào))，簡(jiǎn)稱時(shí)間復(fù)雜度。
對(duì)于求解矩陣相乘問題，算法耗費(fèi)時(shí)間: T(n)= 2n3+ 3n2+2n＋1。
上面例子中T(n)和n3具同階或同數(shù)是級(jí)，引入大"O記號(hào)，則T(n）可記作:T(n)=0(n3)。

算法中基本語句重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n),算法的時(shí)間量度記作:

T(n) = O(f(n))

基本語句是算法中重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間成正比的語句；對(duì)算法運(yùn)行時(shí)間的貢獻(xiàn)最大；執(zhí)行次數(shù)最多。
n越大算法的執(zhí)行時(shí)間越長(zhǎng)（排序：n為記錄數(shù)；矩陣：n為矩陣的階數(shù)；多項(xiàng)式：n為多項(xiàng)式的項(xiàng)數(shù)；集合：n為元素個(gè)數(shù)；樹：n為樹的結(jié)點(diǎn)個(gè)數(shù)；圖：n為圖的頂點(diǎn)數(shù)或邊數(shù)）。

計(jì)算時(shí)間復(fù)雜度

一般情況下，不必計(jì)算所有操作的執(zhí)行次數(shù)，而只考慮算法中基本操作執(zhí)行的次數(shù)，它是問題規(guī)模n的某個(gè)函數(shù)，

方法步驟

• ①找出語句頻度最大的那條語句作為基本語句。（執(zhí)行次數(shù)最多的語句）
• ②計(jì)算基本語句的頻度的得到問題規(guī)模n的某個(gè)函數(shù)f(n)。（最難最關(guān)鍵）
• ③取其數(shù)量級(jí)用符號(hào)“O”表示。

例子：（一些例子涉及到高數(shù)的級(jí)數(shù)了，很陌生了，頭疼，先暫時(shí)忽略）

void exam(float x[][], int m, int n)
{
    float sum[];
    for(int i = 0; i < m; i++)   //執(zhí)行m+1次
    {
        sum[i] = 0.0;
        for(int j = 0; j < n; j++)//執(zhí)行（n+1）*m次
        {
            sum[i] += x[i][j];//嵌套最深層語句  執(zhí)行m*n次
        }
    }
    for(i = 0; i < m; i++)
    {
        cout << i << ":" << sum[i] << endl;
    }
}

f(n)= m*n;
時(shí)間復(fù)雜度表示為：T（n）= O(m*n);

for(i = 1; i <= n; i++){
    for(j = 1; j <= i; j++){
        for(k = 1; k <= j; k++){
            x = x + 1;
        }
    }
}

下面這個(gè)是考研的真題：

//分析以下程序段的時(shí)間復(fù)雜度
i = 1;//語句1
while(i <= n){
    i = i * 2;//語句2
}

復(fù)雜度比較

小結(jié)

基本到這里就結(jié)束了緒論的學(xué)習(xí)，大概記錄這些了！

參考資料：
青島大學(xué).王卓.數(shù)據(jù)結(jié)構(gòu)與算法
《數(shù)據(jù)結(jié)構(gòu) C語言版》.嚴(yán)蔚敏

歡迎關(guān)注本人微信公眾號(hào)：那個(gè)混子

記錄自己學(xué)習(xí)的過程，分享樂趣、技術(shù)、想法、感悟、情感！

單片機(jī)類嵌入式交流學(xué)習(xí)可加企鵝群：120653336