久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

標題: 算法分析與設(shè)計筆記(一) 算法引論 [打印本頁]

作者: 51hei人人 時間: 2016-3-12 15:51
標題: 算法分析與設(shè)計筆記(一) 算法引論
本帖最后由 51hei人人于 2016-3-12 15:53 編輯

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

歡迎光臨 (http://www.zg4o1577.cn/bbs/)