本帖最后由 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.zg4o1577.cn/bbs/dpj-46009-1.html
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
