算法的基本概念

ID:107189 · 發(fā)表于 2016-3-5 18:30

基本概念

1、算法：規(guī)則的有序有限集合; 規(guī)則是有確切含義而無(wú)二義性.

2、算法的基本特征：

可終止性;算法必須在有限時(shí)間內(nèi)終止;

正確性;算法必須正確描述問(wèn)題的求解過(guò)程;

可行性：算法必須是可實(shí)施的;

算法可以有0個(gè)或0個(gè)以上的輸入;

算法必須有1個(gè)或1個(gè)以上的輸出

算法的描述

規(guī)則采用自然語(yǔ)言或算法流程控制采用結(jié)構(gòu)化程序的基本控制結(jié)構(gòu)(順序、選擇、重復(fù))描述.形式語(yǔ)言描述;

算法與程序的關(guān)系

1.程序可以不一定滿足可終止性。但算法必須在有限時(shí)間內(nèi)結(jié)束;

2.程序可以沒(méi)有輸出,而算法則必須有輸出;

3.算法是面向問(wèn)題求解的過(guò)程描述，程序則是算法的實(shí)現(xiàn).

復(fù)雜度

算法復(fù)雜度：評(píng)價(jià)算法優(yōu)劣的唯一標(biāo)準(zhǔn)。由時(shí)間復(fù)雜度和空間復(fù)雜度構(gòu)成.

時(shí)間復(fù)雜度:算法執(zhí)行所花費(fèi)的時(shí)間;

空間復(fù)雜度:算法執(zhí)行所占用的內(nèi)存.

設(shè)n為問(wèn)題的大小(即問(wèn)題所處理元素的個(gè)數(shù)),則時(shí)間復(fù)雜度函數(shù)記為T(n),空間復(fù)雜讀S(n)。

復(fù)雜度分析

事前分析是算法分析的重要步驟，是在算法實(shí)現(xiàn)之前進(jìn)行時(shí)間和空間復(fù)雜度分析。

時(shí)間復(fù)雜度分析：就是對(duì)已設(shè)計(jì)好的算法進(jìn)行有效的時(shí)間。

采用的基本方法是按照算法的控制結(jié)構(gòu)進(jìn)行分析，首先確定問(wèn)題求解的基本操作，然后按照三種控制結(jié)構(gòu)分別進(jìn)行基本操作數(shù)與問(wèn)題處理量的關(guān)系，確定出問(wèn)題的時(shí)間復(fù)雜度函數(shù)。

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

時(shí)間復(fù)雜度分為最壞情況的復(fù)雜度和平均情況的復(fù)雜度。

在這里對(duì)時(shí)間復(fù)雜度分析我們只進(jìn)行最壞情況的復(fù)雜度分析，基本方法如下所述：

每條規(guī)則的時(shí)間復(fù)雜度直接確定

順序結(jié)構(gòu)：采用加法法則；重復(fù)結(jié)構(gòu)：采用乘法法則；分支結(jié)構(gòu)：采用取最大值法則。

最壞情況和平均情況分析

最壞情況分析：在時(shí)間復(fù)雜度分析中，最壞情況是指在所有大小為n的輸入中，選擇代價(jià)最大的狀態(tài)進(jìn)行分析而獲得的時(shí)間復(fù)雜度;

平均情況分析：平均情況分析是指在所有大小為n的輸入中，首先確定每個(gè)輸入出現(xiàn)的概率，針對(duì)每個(gè)輸入及其出現(xiàn)的概率的進(jìn)行分析而獲得的時(shí)間復(fù)雜度.

基本運(yùn)算

定義：如果算法中的一個(gè)元運(yùn)算具有最高頻度，所有其它元運(yùn)算頻度均在它的頻度的常數(shù)倍數(shù)之內(nèi)，則稱這個(gè)元運(yùn)算為基本運(yùn)算。

在分析搜索和排序算法時(shí)，若元素比較為元運(yùn)算，則為基本運(yùn)算。

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

時(shí)間復(fù)雜度采用量級(jí)關(guān)系描述。

設(shè)時(shí)間復(fù)雜度函數(shù)為T(n), 則將T(n)描述為T(n) =O(f(n))，其含義為當(dāng)n趨于無(wú)窮大時(shí)，T(n)和f(n)的比為一個(gè)不等于0的常數(shù)。

一般情況下f(n)為一個(gè)簡(jiǎn)單函數(shù)，通常有以下形式：C,n,long(n),n!,n的冪等等一些描述簡(jiǎn)單的函數(shù).

遞歸方程求解的方法

展開(kāi)遞推式；

代入法；利用已知方程的解代入；

利用生成函數(shù)求解；生成函數(shù)是組合數(shù)學(xué)的一種方法；

歸納法在算法復(fù)雜度分析中是一種常用的求解方法，根據(jù)算法的流程，可構(gòu)造復(fù)雜度函數(shù)。

分治方法的基本思想

當(dāng)被求解的問(wèn)題規(guī)模n較大，不能直接求解時(shí)，可以將該問(wèn)題分成若干個(gè)規(guī)模較小的子問(wèn)題；

若子問(wèn)題仍不能求解，則繼續(xù)進(jìn)行劃分，直到子問(wèn)題可直接求解；

最后由子問(wèn)題的解歸并出原問(wèn)題的解。

分治方法的基本模式

Divde & conquer(n)

{if (n<=n0) qwt(n);

else {Divide n into subinstances n1,n2,…,nm;

for ( i=1,i<=m,i++)

yi=Divde & conquer(ni);}

return merge(y1,y2,…,ym);}

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃和分治法相似,也是把待求解問(wèn)題劃分成若干個(gè)子問(wèn)題,先求解子問(wèn)題,然后,從這些子問(wèn)題的解得到原問(wèn)題的解.所不同的是動(dòng)態(tài)規(guī)劃所分解的子問(wèn)題不是獨(dú)立的.

動(dòng)態(tài)規(guī)劃通常用于求解最優(yōu)性質(zhì)的問(wèn)題

最佳原理:不論以前狀態(tài)如何,當(dāng)前狀態(tài)的值取決于它的所有直接前驅(qū)的狀態(tài);

最優(yōu)化原理：給出一個(gè)最優(yōu)的決策序列，每一個(gè)子序列自身必須上最優(yōu)的決策序列

基本思想

動(dòng)態(tài)規(guī)劃采用最佳原理,對(duì)問(wèn)題從初始狀態(tài)逐步求解,找出最優(yōu)解.描述如下:

1)找出最優(yōu)解的性質(zhì),并描述其結(jié)構(gòu);

2)遞歸地定義最優(yōu)值;

3自底向上計(jì)算最優(yōu)值，記錄相關(guān)信息，最終構(gòu)造最優(yōu)最優(yōu)解；

4）根據(jù)記錄信息，最終構(gòu)造最優(yōu)最優(yōu)解；

最優(yōu)策略

動(dòng)態(tài)規(guī)劃可以找出問(wèn)題的最幼解，但是獲取最佳解的計(jì)算過(guò)程復(fù)雜且計(jì)算量很大，幾乎是列出所有解，才能找出最佳解。

對(duì)于任意問(wèn)題，通常會(huì)存在一類約束條件和一些輸入，任何滿足這些約束條件的子集可以稱為問(wèn)題的一個(gè)可能解。最佳解則是滿足目標(biāo)函數(shù)達(dá)到最大值或最小值的一個(gè)可能解。

基本思想

最優(yōu)策略也是一個(gè)多步?jīng)Q策方法.每一步的選擇都使得能構(gòu)成問(wèn)題的一個(gè)可能解，同時(shí)使目標(biāo)函數(shù)值的增速加快(目標(biāo)函數(shù)最大)或減小(目標(biāo)函數(shù)最小),這種選擇過(guò)程以一些最優(yōu)化度量為根據(jù).

最優(yōu)化度量的選擇方法也稱為貪心法.

回溯法

一般方法:回溯法的基本策略是搜索(按深度優(yōu)先進(jìn)行).

回溯法將問(wèn)題的解表示成一個(gè)n元式(x1,x2,…,xn),其中每個(gè)xi取自某一初值集合si，稱(x1,x2,…,xn)為問(wèn)題的解向量.

回溯法求解問(wèn)題的過(guò)程需要滿足某種條件(稱為約束條件)或者使問(wèn)題的解滿足判定函數(shù)B(x1,x2,…,xn)極大化(或極小化),希望求出約束條件或者判定函數(shù)某個(gè)解向量或所有解向量.

解空間:包含問(wèn)題所有解的一棵樹(shù)稱為解的狀態(tài)空間樹(shù);

從根結(jié)點(diǎn)出發(fā)搜索解的狀態(tài)空間樹(shù),對(duì)于每一個(gè)結(jié)點(diǎn),判定該結(jié)點(diǎn)是否滿足約束條件和判定函數(shù),若滿足,則進(jìn)入一個(gè)孩子樹(shù)繼續(xù)搜索,否則返回其雙親結(jié)點(diǎn),進(jìn)入其另一個(gè)孩子樹(shù)進(jìn)行搜索,直到求出問(wèn)題所要求的解.

算法描述

1）對(duì)于n元式(x1,x2,…,xn),定義每一個(gè)分量的取值范圍；

2）定義約束條件P(X)和判定函數(shù)B(X)；

3）設(shè)i=1;

4)對(duì)第i個(gè)元素賦一個(gè)可能值;使X =( x1,x2,…,x i);若所有可能值已經(jīng)全部使用,則 i --; 重復(fù)4;

5)當(dāng)P(X)和B(X)為真時(shí). i ++;進(jìn)入6,否則i --: 返回4:

6)由X =(x i)構(gòu)造x i +1:返回5:

7)直到求出一個(gè)(或所有)滿足約束條件P(X)和判定函數(shù)B(X)的解。

遞歸算法

Backseach(i)

{if (i>n) output(X);

else {X=(xi);