標(biāo)題: 算法分析與設(shè)計(jì)筆記(一) 算法引論 [打印本頁]
作者: 51hei人人    時(shí)間: 2016-3-12 15:51
標(biāo)題: 算法分析與設(shè)計(jì)筆記(一) 算法引論
本帖最后由 51hei人人 于 2016-3-12 15:53 編輯

1.算法:描述一種算術(shù)運(yùn)算的過程。
2.算法的五個(gè)重要特征:1.有窮性2.確定性3.有0個(gè)或者多個(gè)輸入4.有一個(gè)或者多個(gè)輸出5.可行性(能再有限的時(shí)間內(nèi)完成).
3.算法描述(教材采用偽代碼)。
4.一個(gè)簡(jiǎn)單問題的求解過程:問題分析、算法分析、算法設(shè)計(jì)、算法實(shí)現(xiàn)。
5.評(píng)價(jià)算法的三條主要標(biāo)準(zhǔn)：1.算法實(shí)現(xiàn)所耗費(fèi)的時(shí)間2.算法實(shí)現(xiàn)所耗費(fèi)的空間3.算法應(yīng)易于理解、編碼、調(diào)試。
6.算法的時(shí)間復(fù)雜度(四條定義,一條定理)
　　影響因素:1.數(shù)據(jù)結(jié)構(gòu)2.數(shù)學(xué)模型3.設(shè)計(jì)策略4.問題規(guī)模5.設(shè)計(jì)語言6.機(jī)器代碼質(zhì)量7.執(zhí)行速度。
　　分析方法：1.事后測(cè)試2.事前分析。
　　定義1:在問題規(guī)模為n的算法中，如果存在二個(gè)正常數(shù)C和n0,對(duì)任意n>=n0,都有|g(n)|<=C|f(n)|則記作|g(n)|=O(f(n))。0為數(shù)量級(jí)。
　　定義2:算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間度量記作T(n)=O(f(n))
　　定義3:如果存在二個(gè)正數(shù)C和n0，對(duì)任意n>n0都有|g(n)|>=C|f(n)|則記為g(n)=Ω(f(n))。表明f(n)是g(n)的下界函數(shù)。
　　定義4:如果存在正常數(shù)C1,C2和n0,對(duì)于所有的n>n0,有C1|f(N)|<=|G(N)|<=c2|F(N)|則記為g(n)=θ(f(n))。
　　定理：若A(n)=amnm+...+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)。
7.算法的空間復(fù)雜度
　　算法在執(zhí)行過程中所占存儲(chǔ)空間的大小S(n)。S(n)=O(f(n))。
8.NP-完全問題
　　當(dāng)一個(gè)問題滿足:1.A屬于NP;2.對(duì)于任意問題B，如果B屬于NP時(shí)，總有B<=pA.則稱該問題是NP完全的。
9.基本的數(shù)據(jù)結(jié)構(gòu)
　　棧和隊(duì)列。
　　棧：一種只允許在表的一端進(jìn)行插入或刪除操作的線性表。能插入、刪除的一端為棧頂，另一端為棧底。插入：進(jìn)棧。刪除：出棧。
　　順序棧的數(shù)據(jù)結(jié)構(gòu)：
　　typedef struct{
　　1　　SElemType * base;
　　2　　SElemType * top;
　　3　　int stacksize;
　　4 }sqStack;
　　進(jìn)棧算法：Push(sqStack &S,SElemType e)
　　　　　　　　　//向順序棧中插入元素e作為新的棧頂元素
　　　　　　　1　　if S.top-S.base>=stacksize　　//如果棧滿，則追加存儲(chǔ)空間
　　　　　　　2　　then {
　　　　　　　3　　　　　 if S.base=NULL
　　　　　　    4　　　　      　　then exit; 　　　　//存儲(chǔ)分配失敗
　　　　　　    5　　　　　　S.top <-S.base+S.stacksize;
　　　　　　　6　　　　　　S.stacksize<-S.stacksize+stackincrement;}
　　　　　　　7　　*S.top<-e;
　　　　　　    8        S.top<-S.top+1;
　　出棧算法：Pop(sqStack &S,SElemType &e)
　　　　　　　　//若棧不空，則刪除S的棧頂元素，用e返回其值,并返回OK；否則返回ERROR
　　　　　　　　1　　if S.top=S.base
　　　　　　　　2　　　　then return ERROR;
　　　　　　　　3　　S.top<-S.top-1;
　　　　　　　　4　　e<-*S.top;
　　　　　　　　5　　return OK;
　　鏈?zhǔn)綏５臄?shù)據(jù)結(jié)構(gòu)：
　　typedef struct LStack{
　　1　　　　SElemType data;
　　2　　　　struct　LStack　*next;
　　3　　}LStack;
　　進(jìn)棧算法：Push(LStack &S,SElemType e)
　　　　　　　　1　　S<-(LStack *)malloc(sizeof(LStack));
　　　　　　　　2　　S.data<-e;
　　　　　　　　3　　S.next<-p;
　　　　　　　　4　　p<-S;
　　出棧算法：Pop(LStack &S,SELemType e)
　　　　　　　　1　　 if NULL=p.next
　　　　　　　　2　　　　then return ERROR;
　　　　　　　　3　　e<-p.data;
　　　　　　　　4　　q<-p;
　　　　　　　　5　　p<-p.next;
　　　　　　　　6　　free(q);
　　　　　　　　7　　return OK;
下接：算法設(shè)計(jì)筆記（二）算法概論:http://www.torrancerestoration.com/bbs/dpj-46009-1.html






歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1