欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

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

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

1.算法:描述一種算術運算的過程。
2.算法的五個重要特征:1.有窮性2.確定性3.有0個或者多個輸入4.有一個或者多個輸出5.可行性(能再有限的時間內完成).
3.算法描述(教材采用偽代碼)。
4.一個簡單問題的求解過程:問題分析、算法分析、算法設計、算法實現。
5.評價算法的三條主要標準：1.算法實現所耗費的時間2.算法實現所耗費的空間3.算法應易于理解、編碼、調試。
6.算法的時間復雜度(四條定義,一條定理)
　　影響因素:1.數據結構2.數學模型3.設計策略4.問題規模5.設計語言6.機器代碼質量7.執行速度。
　　分析方法：1.事后測試2.事前分析。
　　定義1:在問題規模為n的算法中，如果存在二個正常數C和n0,對任意n>=n0,都有|g(n)|<=C|f(n)|則記作|g(n)|=O(f(n))。0為數量級。
　　定義2:算法中基本操作重復執行的次數是問題規模n的某個函數f(n)，算法的時間度量記作T(n)=O(f(n))
　　定義3:如果存在二個正數C和n0，對任意n>n0都有|g(n)|>=C|f(n)|則記為g(n)=Ω(f(n))。表明f(n)是g(n)的下界函數。
　　定義4:如果存在正常數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.算法的空間復雜度
　　算法在執行過程中所占存儲空間的大小S(n)。S(n)=O(f(n))。
8.NP-完全問題
　　當一個問題滿足:1.A屬于NP;2.對于任意問題B，如果B屬于NP時，總有B<=pA.則稱該問題是NP完全的。
9.基本的數據結構
　　棧和隊列。
　　棧：一種只允許在表的一端進行插入或刪除操作的線性表。能插入、刪除的一端為棧頂，另一端為棧底。插入：進棧。刪除：出棧。
　　順序棧的數據結構：
　　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;
　　鏈式棧的數據結構：
　　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;
下接：算法設計筆記（二）算法概論:http://www.raoushi.com/bbs/dpj-46009-1.html

歡迎光臨 (http://www.raoushi.com/bbs/)