本帖最后由 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.51hei.com/bbs/dpj-46009-1.html
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
