算法和算法分析概念

1 算法及其性能标準

算法是求解一類問題的任意一種特殊的方法，較嚴格的來說，是對特定問題的求解步驟的一種描述，它是指令的有限序列。

算法的五個特征：輸入、輸出、确定性、能行性、有窮性

衡量一個算法的性能，主要有以下标準：正确性，簡明性，健壯性，效率。

2 算法的時間複雜度

判斷算法的性能要考慮的一個基本特征就是問題執行個體的規模，規模一般是輸入量（有時也涉及輸出量）。

算法的事前分析：在排除程式運作環境的因素後來讨論算法的時間效率。

算法的事後測試：測試一個程式在所選擇的的輸入資料下運作時實際所需要的時間。

程式步：文法或語義上有意義的程式段。

程式步的計算執行個體：

求一個數組元素累加之和的遞歸程式，

float Sum(float list[],int n)
	{
		count++;	//針對if條件
		if(n)
		{
			count++;	//針對下面的一條語句
			return Sum(list,n-1) + list[n-1];
		}
		count++;
		return 0;	//針對return語句
	}
           

當 n = 0 時，所需步數為 2 ；

當 n > 0 時，執行語句和第一句 return;則可表示為

T(n) = 2 + T(n-1) = 2 + 2 + T(n-2)

 = 2 + 2 + 2 + T(n-3)

 = 2n + T(0)

 = 2n + 2

程式步不能确切地反映程式運作的實際時間。

3 漸進時間複雜度

定義：設f(n)和g(n)是定義在正整數上的正函數，如果存在兩個正常數c和n0，使得當n>=no時，有f(n)<=cg(n),則記作f(n) = O(g(n)),被稱為大O記号(big-Oh notation)

 大O記号用以表達一個算法運作時間的上界。當我們說一個算法具有O(g(n))的運作時間時，是指該算法在計算機上的實際運作時間不會超過g(n)的一個常數倍。

例：設一個程式的實際執行時間T(n) = 3.6 n^3 + 2.5 n^2 + 2.8 ,則T(n) = O(n^3),O(1)表示常數計算時間，計算法隻需執行有限程式步。

注：1bn = log2 n

漸近時間複雜度按從小到大的順序排列為O(1)<O(1b)<O(n)<O(n1bn)<O(n^2)<O(n^3)