前言

學習資料結構，演算法是基礎，本篇主要介紹演算法及其復雜度，附例子及代碼，

一、什么是演算法

1.定義:
演算法：
一個有限指令集
接受一些輸入（有些情況下不需要輸入）
產生至少一個輸出
一定在有限步驟之后終止
每一條指令必須：
（1）有充分明確的目標，不可以有歧義
（2）在計算機能處理的范圍之內
（3）描述要抽象，不應該依賴于任何一種計算機語言以及具體的實作手段

2.演算法的描述工具：
1.自然語言
2.程式設計語言
3.流程圖（框圖）
4.偽碼語言：
包括 高級程式設計語言的三種基本結構（順序、選擇、回圈）和 自然語言成分
5.類c語言：
介于偽碼語言和程式設計語言之間的一種表現形式，保留了C語言的精華，不拘泥于C語言的語法細節，同時添加了一些C++的成分
特點：便于理解、閱讀；能方便的轉換成C語言

3.演算法的主題：
<1>函式：用以表示演算法
函式型別 函式名 （函式引數表）
{ //演算法說明
陳述句序列
}//函式名
注：（1）演算法說明應包括功能說明，輸入、輸出；
（2）為提高演算法可讀性，關鍵位置加以說明；
（3）明確函式實參和形參的匹配規則，以便能正確使用演算法函式
<2> 其他說明可附在函式定義后

4.舉例
（1）選擇排序演算法的偽碼描述：
其中有兩處抽象：
1.list到底是陣列還是鏈表
2.swap用函式還是宏去實作

void SelectionSort (int List[], int N)
{
	//將 N 個整數進行遞增排序
	for (i=0;i<N;i++)
	{
		//從List[i]到List[N-1]中找最小元，并將其位置賦給MinPosition
		MinPosition = ScanFormin( List i,N-1);
		//將未排序部分的最小元換到有序部分的最后位置 
		Swap(List[i],List[Minposition]); 
	 } 
 }

（2）演算法描述舉例
問題：設一維陣列 a[0…n-1]中有n個整數，其中n為常數，試設計演算法：求陣列中所有元素最大值
用偽碼來表示演算法的主要思想:
1.maxai = a[0];
2.i = 1;
3.若i <= n-1,則：
3.1 若a[i] > maxai,則 maxai = a[i];
3.2 i++;
3.3 轉3
4.maxai為最大值

  *以下為代碼實作*

int a_maxint(int a[],int n)
{
	int j,maxai = a[0];
	for (j=1;j<=n-1;j++)
		if(a[j]>maxai)
			maxai = a[j];
	printf("maxai=&d\n",maxai);
	return maxai
}	

二、什么是好的演算法

1.多項式問題引入

	以多項式為例，比較同一問題不同方法的演算法優劣，使大家對好壞演算法的衡量有初步的判斷與感受，

多項式的表示：
例：一元多項式及其運算
一元多項式： f(x) = a0 + a1*x + … + a(n-1)x^(n-1) + an(x^n)
主要運算：多項式相加、相減、相乘等

分析：如何表示多項式
多項式的關鍵資料：
1.多項式項數 n
2.各項系數 ai 及指數 i

（1）方法1：（最簡）順序存盤的直接表示
陣列各分量對應多項式各項：
a[i]：項 x^i的系數 ai
下標 i：x的指數
兩個多項式相加：兩個陣列對應分量相加
PS:存在問題，當 x次數很高，要用一個很大的陣列

（2）方法2：順序存盤結構表示非零項,節省空間，同樣也方便運算
①每一項按照指數大小有序存盤，下面例子中指數大的排在前面，指數小的排在后面
②每個非零項涉及兩個資訊：系數 ai 和指數 i，可將一個多項式看成是一個（ai,i)二元組的集合
③用結構陣串列示：陣列分量是由系數 ai，指數 i組成的結構，對應一個非零項

eg：P1(x)=9x^12 +15*x^8 + 3x^2
P2(x)=26x^19 - 4x^8 - 13x^6 + 82
下標i 0 1 2 …
系數 ai 9 15 3 …
指數 i 12 8 2 …
//相加程序：從頭開始，比較兩個多項式當前對應項的指數
P1:(9,12),(15,8),(3,2)
P2:(26,19),(-4,8),(-13,6),(82,0)
如先比較p1第一項和p2第一項指數，指數高的則輸出，再比較p1第一項與p2第二項，以此類推
指數一樣則系數相加減
結果：P3：(26,19) (9,12) （11,8） (-13,6) (3,2) (82,0)

（3）方法3：鏈表結構存盤非零項
鏈表中每個結點存盤多項式中的一個非零項，包括系數和指數兩個資料域及一個指標域
系數：coef 指數： expon
指標域：link

typedef struct PolyNode *Polynomial;
struct PolyNode
{
	int coef;
	int expon;
	Polynomial link;
}; 

2. 如何衡量演算法

（1）空間復雜度 S(n):根據演算法寫成的程式，在執行時占用存盤單元的長度，
		注：這個長度往往與輸入資料的規模有關，空間復雜度過高的演算法可能導致使用的記憶體超限，造成程式非正常中斷
（2）時間復雜度 T(n): 根據演算法寫成的程式，在執行時耗費時間的長度，
		注：這個長度往往與輸入資料的規模有關，時間復雜度過高的低效演算法可能導致在有生之年都等不到運行結果
		
		時間復雜度曲線（遞增）
	O(1)<O(log2 n)< O(n)< O(nlog2 n)< O(n^2)< O(n^3) <O(2^n) 					

分析一般演算法效率，經常關注：
1.最壞情況復雜度 Tworst(n)
2.平均復雜度 Tavg(n)
后者<=前者
分析前者較多

*以下舉幾個例子計算兩種復雜度

eg1：遞回列印整數 ：s(N) = C·N
注：若使用回圈，不管 N 多大，始終占用一個固定的空間，空間復雜度更低

#include <stdio.h>
void PrintN (int N)
{
	if (N){
		PrintN (N-1);
		printf ("%d\n",N);
	}
	return ;
}
int main()
{
	int a=10;
	PrintN(a);
	return 0;
}

eg2.1：多項式的例子，計算T(n),計算做了多少次乘除法即可，加減法可忽略
T(n) = C1n^2+C2n

double f (int n,double a[],double x)
{
	int i;
	double p=a[0];
	for (i=1;i<=n;i++)
		p += (a[i] * pow(x,i));// 一個回圈內做 i 次，共做了(n*n+n)/2次乘法 
	return p;
 } 

eg2.2:T(n) = C*n

double f (int n,double a[],double x)
{
	int i;
	double p=a[0];
	for (i=n;i>0;i--)
		p = a[i-1] + x*p;//一個回圈內1次乘法，共n次 
	return p;
 }

3.4個例子細說復雜度

（1）eg1：O(1)稱為：常量階/常量數量級

{
	int s;
	scanf("%d",&s);
	s++;
	printf("&d",s);
} 

其中:陳述句頻度為 f(n)=f(1)=3
時間復雜度 T(n)=O(f(n))=O(3)=O(1)

（2）O(n)稱為線性階/線性數量級

void sum (int a[],int n)
{
	int s = 0,i;//1次
	for (i=0;i<n;i++)//n次
		s = s+a[i];//n次 
	printf ("&d",s);//1次 
}

陳述句頻度：f(n)=1+n+n+1
時間復雜度 T(n)=O(f(n))=O(2n+2)=O(n)

（3）eg3:O(n^2)稱為平方階/平方數量級

void sum (int m,int n)
{
	int i,j,s = 0;// 1次
	for (i=1li<=m;i++)//m次
	{
		for (j=1;j<=n;j++)//m*n次
			s++;//m*n次
		printf("&d",s);//m次 
	} 
}

f(m,n)=1+m+2mn+m=2mn+2m+1
當m=n,f(n)=2n^2+2n+1
T(n)=O(f(n))=O(2n+1+2n^2)=O(n*n)

（4）eg4：冒泡排序

void bubble1 (int a[],int n)
{
	int i,j,temp;
	for (i=1;i<n;i++)//n-1次
		for (j=0;j<n-i;j++)//n(n-1)/2次
			if(a[j]>a[j+1])//n(n-1)/2次
			{
				temp = a[j];//n(n-1)/2或0 次
				a[j] = a[j+1];//n(n-1)/2或0次
				a[j+1] = temp; //n(n-1)/2或0次
			}
	
	for (i=0;i<n;i++)//n 
		printf("&d",a[i]);//n
}

最壞情況：每次比較都發生資料交換,n^2+2n-1
最好情況：每次比較都不發生資料交換,5n^2/2 + n/(2-1)
T最好=T最壞=O(n^2)

4.復雜度的漸進表示法

（1）	**上下界有很多，找最貼合的上下界**
	T(n)=O(f(n)) 表示存在常數 C>0,n0>0 使得當 n>=n0時有 T(n)<=C*f(n),即 f(n) 是 T(n)的上界 
		T(n) = Ω(g(n)) 表示存在常數 C>0,n0>0 使得當 n>=n0時有 T(n)>=C*f(n),即 g(n) 是 T(n)的下界
		T(n) = θ(h(n)) 表示同時有 T(n)=O(h(n))和 T(n)=Ω(h(n))
		
	（2）另附：復雜度分析小竅門：
	1.若兩段演算法分別有復雜度 T1(n)=O(f1(n))和 T2(n)=O(f2(n)) ，則
		T1(n) + T2(n) = max(Of1(n),Of2(n)) 
		T1(n) * T2(n) = O(f1(n)* f2(n))
	2.若 T(n)是關于 n 的 k 階多項式，那么 T(n)= θ(n^k)
	3.一個for回圈的時間復雜度=回圈次數*回圈體代碼復雜度
	4.if-else結構的復雜度取決于if的條件判斷復雜度和兩個分支的復雜度總體復雜度取三者中最大

三.應用實體——最大子列和問題

這里以最大子列和問題，提出4種不同的演算法，對演算法的優劣比較進行更深層剖析，

題目：給定 N個整數的序列 {A1,A2,…,An},函式 f(i,j)=max{0,求和:從 Ai到Aj} ，求函式的最大值，若和為負數，則回傳0
ps：以下代碼均為函式

（1）演算法1：把所有的連續子列和全部算出來，從中找最大的那一個
復雜度 T(n)=O(n^3) ，三重回圈嵌套

int MaxSubseqSum1 (int A[],int N)
{
	int ThisSum,MaxSum = 0;
	int i,j,k;
	for (i=0;i<N;i++)//i為子列左端位置 
	{
		for (j=i;j<N;j++)//j為子列右端位置 
		{
			ThisSum = 0;//ThisSum是從A[i]到A[j]的子列和
			for (k=i;k<=j;k++)
			{
				ThisSum += A[k];
			}
			if (ThisSum > MaxSum) //若剛得到的子列和更大，則更新結果
				 MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

（2）演算法2：把所有的連續子列和全部算出來，從中找最大的那一個，k回圈作廢
復雜度 T(n)=O(n^2) ，兩重回圈嵌套

int MaxSubseqSum2 (int A[],int N)
{
	int ThisSum,MaxSum = 0;
	int i,j,k;
	for (i=0;i<N;i++)//i為子列左端位置 
	{
		ThisSum = 0;//ThisSum是從A[i]到A[j]的子列和
		for (j=i;j<N;j++)//j為子列右端位置 
		{
			ThisSum += A[j];//對于相同的i，不同的j，只要在前一次回圈的基礎上累加1項即可 
			if (ThisSum > MaxSum) //若剛得到的子列和更大，則更新結果
				 MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

（3）演算法3：分而治之
運算程序：復雜度 T(n)=左邊復雜度+右邊復雜度+跨越中間復雜度 =2T(n/2)+cn
把 T(n/2)展開得，左邊=4T(n/4)+2cn ,繼續展開得
左邊=+ckn+ 2^kO(1)
其中n/(2^k)=1
則左邊=nO(1)+cn*log2 n ，n=1時是常數
相加時取較大那一項，即 O(NlogN）

遞回：從中間開始不停的對半分，算出分界線兩邊的最大子列和，再算出跨越分界線的最大子列和，即可得出結論

int Max3(int A,int B,int C)//回傳3個整數中的最大值 
{
	return A > B ? A > C ?A : C : B > C ? B : C;
}
int DivideAndConquer (int List[],int left,int right)//分治法求List[left]到List[right]的最大子列和 
{
	int MaxLeftSum,MaxRightSum;//存放左右子問題的解 
	int MaxLeftBorderSum,MaxRightBorder;//存放跨分界線的結果
	int LeftBorderSum,RightBorder;
	int center,i;
	
	if (left==right)//遞回終止條件，子列僅1個數字
	{
		if (List[left]>0)
			return List[left];
		else return 0;
	}

	//以下為“分”
	center = (left + right)/2;//找到中分點，遞回求兩邊子列最大和
	MaxLeftSum = DivideAndConquer (List,left,center);
	MaxRightSum = DivideAndConquer (List,center,right);
	
	//下面求跨分界線的最大子列和
	MaxLeftBorderSum = 0;
	LeftBorderSum = 0; 
	for (i=center;i>=left;i--)//從中線向左掃描 
	{
		LeftBorderSum += List[i];
		if (LeftBorderSum>MaxLeftBorderSum)
			MaxLeftBorderSum = LeftBorderSum;
	}//左邊掃描結束
	MaxRightBorderSum = 0;
	RightBorderSum = 0; 
	for (i=center+1;i<=Right;i++)//從中線向右掃描 
	{
		RightBorderSum += List[i];
		if (RightBorderSum>MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	}//右邊掃描結束 
	
	//下面回傳“治”的結果
	return Max3 (MaxLeftSum,MaxRight,MaxLeftBorderSum+MaxRightBorderSum); 
}
int MaxUbseqSum3 (int List[],int N)//保持與前兩種演算法相同的函式介面
{
	return DivideAndConquer (List,0,N-1);//呼叫函式 
}

（4）演算法4：在線處理
在線：每輸入一個資料就能進行即時處理，在任何一個地方中止輸入，演算法都能正確給出當前的解
復雜度 T(n)=O(n),線性，副作用：難以理解

int MaxSubseqSum4 (int A[],int N)
{
	int ThisSum,MaxSum;
	int i;
	ThisSum = MaxSum = 0;
	for (i=0;i<N;i++)//i為子列左端位置 
	{
		ThisSum += A[i];//向右累加 
		if (ThisSum > MaxSum) //若剛得到的子列和更大，則更新結果
			 MaxSum = ThisSum;
		else if (ThisSum<0)//若當前子列和為負數，則不可能使后面的部分和增大，拋棄
			ThisSum = 0; 
	}
	return MaxSum;
}

總結

以上簡要介紹演算法復雜度，通過幾個例子進行比較，會更詳細一些，感興趣可以去找找復雜度的函式圖形，會更加直接一些，
如有錯誤，歡迎指正，
ps：內容是聽完網課后自己整合的，代碼非原創，