目錄
一.算法的定義
二.算法的特性
????1.輸入輸出
????2.有窮性
????3.確定性
????4.可行性
三.算法設(shè)計(jì)的要求
????1.正確性
????2.可讀性
????3.健壯性
????4.時(shí)間效率高和存儲(chǔ)量低
四.算法效率的度量方法
????1.事后統(tǒng)計(jì)方法
????2.事前估計(jì)分析方法
五.算法時(shí)間復(fù)雜度.
????1.算法時(shí)間復(fù)雜度定義
????2.推導(dǎo)大O階方法
????3.常數(shù)階
????4.線性階
????5.對(duì)數(shù)階
????6.平方階
六.常見(jiàn)的時(shí)間復(fù)雜度
七.最壞情況與平均情況
八.算法空間復(fù)雜度

一.算法的定義

1.算法定義：

算法是解決特定問(wèn)題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作

二.算法的特性

算法具有五個(gè)基本特性：輸入、輸出、有窮性、確定性和可行性

1.輸入輸出

算法具有零個(gè)或多個(gè)輸入 ，至少有一個(gè)或多個(gè)輸出

2.有窮性

有窮性：指算法在執(zhí)行有限的步驟之后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無(wú)限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成

3.確定性

確定性：算法的每一步驟都具有確定的含義，不會(huì)出現(xiàn)二義性。算法在一定條件下，只有一條執(zhí)行路徑，相同的輸入只能有唯一的輸出結(jié)果。算法的每個(gè)步驟被精確定義而無(wú)歧義。

4.可行性

可行性：算法的每一步都必須是可行的，也就是說(shuō)，每一步都能夠通過(guò)執(zhí)行有限次數(shù)完成。

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

1.正確性

(1)定義：

正確性，算法的正確性是指算法至少應(yīng)該具有輸入、輸出和加工處理無(wú)歧義性、能正確反映問(wèn)題的需求、能夠得到問(wèn)題的正確答案

(2)算法的“正確”大體分為四個(gè)層次：

• 一是算法程序沒(méi)有語(yǔ)法錯(cuò)誤
• 二是算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果
• 三是算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說(shuō)明的結(jié)果
• 四是算法程序?qū)τ诰倪x擇的，甚至刁難的測(cè)試數(shù)據(jù)都有滿足要求的輸出結(jié)果

2.可讀性

可讀性：算法設(shè)計(jì)的另一目的是為了便于閱讀、理解和交流。

3.健壯性

健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)處理，而不是產(chǎn)生異?；蚰涿畹慕Y(jié)果

4.時(shí)間效率高和存儲(chǔ)量低

好的算法還應(yīng)該具備時(shí)間效率高和存儲(chǔ)量低的特點(diǎn)，設(shè)計(jì)算法應(yīng)該盡量滿足時(shí)間效率高和存儲(chǔ)量低的需求

四.算法效率的度量方法

1.事后統(tǒng)計(jì)方法

事后統(tǒng)計(jì)方法：這種方法主要是通過(guò)設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低

這種方法有很大缺陷，通常不予采納

2.事前估計(jì)分析方法

事前分析估算方法：在計(jì)算機(jī)程序編制前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。

(1)一個(gè)用高級(jí)程序語(yǔ)言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素：

• 一是算法采用的策略、方法。
• 二是編譯產(chǎn)生的代碼質(zhì)量。
• 三是問(wèn)題的輸入規(guī)模。
• 四是機(jī)器執(zhí)行指令的速度

(2)事前估算方法的理論依據(jù)，通過(guò)算法時(shí)間復(fù)雜度來(lái)估算算法時(shí)間效率

五.算法時(shí)間復(fù)雜度.

1.算法時(shí)間復(fù)雜度定義

(1)定義：

算法時(shí)間復(fù)雜度表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度。其中f(n)是問(wèn)題規(guī)模n的某個(gè)函數(shù)

(2)用大寫O( )來(lái)體現(xiàn)算法時(shí)間復(fù)雜度的記法，我們稱之為大O記法。

2.推導(dǎo)大O階方法

推導(dǎo)大O階方法：

(1)用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。

(2)在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。

(3)如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。

得到的結(jié)果就是大O階?！?/p>

3.常數(shù)階O(1)

int sum = 0,n = 100;      /* 執(zhí)行一次 */
sum = (1 + n) * n / 2;    /* 執(zhí)行一次 */
printf("%d", sum);        /* 執(zhí)行一次 */

4.線性階O(n)

int i;
for (i = 0; i < n; i++)
{
    /* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */
}”

5.對(duì)數(shù)階O(log₂n)

int count = 1;
while (count < n)
{
    count = count * 2;
    /* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */
}

計(jì)算運(yùn)算次數(shù)
由2^x=n得到x=log₂n

6.平方階O(n²)

int i, j;
for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        /* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */
    }
}

六.常見(jiàn)的時(shí)間復(fù)雜度

(1)常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

七.最壞情況與平均情況

(1)平均運(yùn)行時(shí)間是所有情況中最有意義的，因?yàn)樗瞧谕倪\(yùn)行時(shí)間

(2)對(duì)算法的分析，一種方法是計(jì)算所有情況的平均值，這種時(shí)間復(fù)雜度的計(jì)算方法稱為平均時(shí)間復(fù)雜度

(3)另一種方法是計(jì)算最壞情況下的時(shí)間復(fù)雜度，這種方法稱為最壞時(shí)間復(fù)雜度。一般在沒(méi)有特殊說(shuō)明的情況下，都是指最壞時(shí)間復(fù)雜度

八.算法空間復(fù)雜度

(1).算法空間復(fù)雜度的計(jì)算公式記作：

S(n)=O(f(n))
其中，n為問(wèn)題的規(guī)模，f(n)為語(yǔ)句關(guān)于n所占存儲(chǔ)空間的函數(shù)

(2).通常，我們都使用“時(shí)間復(fù)雜度”來(lái)指運(yùn)行時(shí)間的需求，使用“空間復(fù)雜度”指空間需求