一、演算法及其描述

1、演算法是對特定問題求解步驟的一種描述，它是指令的有限序列。

2、演算法具有以下五個重要的特性

（1）有窮性。指演算法在執行有限的步驟之後，自動結束而不會出現無限迴圈，並且每一個步驟在可接受的時間內完成。

（2）確定性。對於每種情況下執行的操作，在演算法中都有確定的含義，不會出現二義性。並且在任何條件下，演算法都只有一條執行路徑。

（3）可行性。演算法的每條指令都是可執行的，即便人藉助紙和筆都可以完成。

（4）輸入性。演算法有零個或多個輸入。大多數演算法中輸入引數是必要的，但對於較簡單的演算法，如計算1+2的值，不需要任何輸入引數，因此演算法的輸入可以是零個。

（5）輸出性。演算法至少有一個或多個輸出。演算法用於某種資料處理，如果沒有輸出，這樣的演算法是沒有意義的，演算法的輸出是和輸入有著某些特定關係的量。

練習：用擅長的語言編寫以下案例

3、演算法描述

通常演算法用一個或者幾個函式（或者方法）描述

（1）函式的返回值通常為布林型別，表示演算法是否成功執行。在有些情況下可以直接用演算法的返回值來區分輸入引數的正確性。

（2）形參列表表示演算法的引數，由輸入引數和輸出引數構成。

（3）函式體實現演算法的功能。

練習：求和問題是當n≥1時求s=1+2+…+n。

輸入引數為n，操作結果為s。

初始條件是n≥1。

當初始條件不滿足，返回False，否則計算出s並返回True。

二、演算法分析

1、演算法的設計目標

正確性。

可使用性。

可讀性。

健壯性。

高時間效能與低儲存量需求。

2、演算法分析目的：分析演算法的時空效率以便改進演算法效能。

3、演算法時間效能分析

（1）演算法分析方式：

事後分析統計方法：編寫演算法對應程式，統計其執行時間。

事前估算分析方法：撇開上述因素，認為演算法的執行時間是問題規模n的函式。

（2）分析演算法的時間複雜度

一個演算法是由控制結構（順序、分支和迴圈三種）和原操作（指固有資料型別的操作，如+、-、*、/、++和--等）構成的。演算法執行時間取決於兩者的綜合效果。

演算法的執行時間取決於控制結構和原操作的綜合效果。

在一個演算法中，執行原操作的次數越少，其執行時間也就相對地越少；執行原操作次數越多，其執行時間也就相對地越多。

演算法中所有原操作的執行次數稱為演算法頻度，這樣一個演算法的執行時間可以由演算法頻度來計量。

（3）計算演算法頻度T(n)

假設演算法的問題規模為n，例如對10個整數排序，問題規模為n就是10。演算法頻度是問題規模n的函式，用T(n)表示。

演算法執行時間大致等於原操作所需的時間×T(n)，也就是說T(n)與演算法的執行時間成正比。為此用T(n)表示演算法的執行時間。比較不同演算法的T(n)大小得出演算法執行時間的好壞。

（4）T(n)採用時間複雜度表示

演算法中執行時間T(n)是問題規模n的某個函式f(n)，記作：

(n) = O(f(n))

"O"的形式定義為：

T(n) = O(f(n))表示存在一個正的常數c，使得當n≥n0時都滿足：|T(n)|≤c|f(n)|

f(n)是T(n)的上界，這種上界可能很多，通常取最接近的上界，即緊湊上界

提示：就是隻求出T(n)的最高階，忽略其低階項和常係數，這樣既可簡化T(n)的計算，又能比較客觀地反映出當n很大時演算法的時間效能。本質上講是一種T(n)最高數量級的比較。

一般地：

各種不同演算法時間複雜度的比較關係如下：

例子：

（5）簡化的演算法時間複雜度分析

一種簡化的演算法時間複雜度分析方法是，僅僅考慮演算法中的基本操作。

所謂基本操作是指演算法中最深層迴圈內的原操作。而演算法執行時間大致等於基本操作所需的時間×其運算次數。所以在演算法分析時，計算T(n)時僅僅考慮基本操作的執行次數。

例子

（5）演算法的最好、最壞和平均時間複雜度

例如，10個1～10的整數序列遞增排序：

注：

演算法時間效能比較：假如求同一問題有兩個演算法：A和B，如果演算法A的平均時間複雜度為O(n)，而演算法B的平均時間複雜度為O(n2)。

一般情況下，認為演算法A的時間效能好比演算法B。

練習：

該演算法的主要時間花費在元素比較上，可以將元素比較看成基本操作。

（1） 演算法在查詢中總是從i=0開始的，如果a[0]=k，則僅僅一次比較就成功找到k，呈現最好情況，所以演算法的最好時間複雜度為O(1)。

（2） 如果a[n-1]=k，則需要n次比較成功找到k，呈現最壞情況，所以演算法的最壞時間複雜度為O(n)。

（3） 考慮平均情況：

a[0]=k時比較1次

a[1]=k時比較2次

…

a[n-1]=k時比較n次

共n種情況，假設等機率，也就是說每種情況的機率為1/n，則平均比較次數=(1+2+…+n)/n=(n+1)/2=O(n)，所以演算法平均時間複雜度為O(n)。

（3）演算法空間效能分析

一個演算法的儲存量包括形參所佔空間和臨時變數所佔空間。在對演算法進行儲存空間分析時，只考察臨時變數所佔空間。

空間複雜度是對一個演算法在執行過程中臨時佔用的儲存空間大小的量度，一般也作為問題規模n的函式，以數量級形式給出，記作：S(n)=O(g(n))。

其中"O"的含義與時間複雜度分析中的相同。

為什麼演算法空間分析只考慮臨時空間，而不必考慮形參的空間呢？

分析演算法的空間複雜度

三、資料結構的目標

1、好演算法設計的過程

採用面向物件的程式設計語言實現抽象資料型別時，通常將一個抽象資料型別設計成一個類，採用類的資料變量表示資料的儲存結構，將抽象運算透過類的公有方法實現。

2、儲存結構對演算法的影響主要在兩方面：

儲存結構的儲存能力

儲存結構應與所選擇的演算法相適應

3、例子

構造集合ADT Set，假設其中元素為整型，遵循標準數學定義，基本運算包括:

另外增加3個集合運算:

求兩個集合並Union、集合交Inter和集合差Diff。

設計儲存結構

設計運算演算法

Set類包含以下基本運算方法：

設計主程式