|
|
本帖最后由 51hei人人 于 2016-3-12 15:53 編輯
1.算法:描述一種算術(shù)運(yùn)算的過(guò)程。
2.算法的五個(gè)重要特征:1.有窮性2.確定性3.有0個(gè)或者多個(gè)輸入4.有一個(gè)或者多個(gè)輸出5.可行性(能再有限的時(shí)間內(nèi)完成).
3.算法描述(教材采用偽代碼)。
4.一個(gè)簡(jiǎn)單問(wèn)題的求解過(guò)程:問(wè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.問(wèn)題規(guī)模5.設(shè)計(jì)語(yǔ)言6.機(jī)器代碼質(zhì)量7.執(zhí)行速度。
分析方法：1.事后測(cè)試2.事前分析。
定義1:在問(wèn)題規(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ù)是問(wèn)題規(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í)行過(guò)程中所占存儲(chǔ)空間的大小S(n)。S(n)=O(f(n))。
8.NP-完全問(wèn)題
當(dāng)一個(gè)問(wèn)題滿足:1.A屬于NP;2.對(duì)于任意問(wèn)題B，如果B屬于NP時(shí)，總有B<=pA.則稱(chēng)該問(wèn)題是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://m.zg4o1577.cn/bbs/dpj-46009-1.html
|
|
