欢迎来到天天文库
浏览记录
ID:38529266
大小:519.50 KB
页数:21页
时间:2019-06-14
《第01章算法与算法复杂性》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、《算法设计与分析》第01章算法与算法复杂性一、算法算法的概念算法的性质算法的描述二、算法复杂性算法复杂性的概念C=F(N,I,A)T(N,I)=∑tiei(N,I)Tmax(N),Tmin(N),Tavg(N)二、算法复杂性复杂性的度量渐近性态上界f(N)=O(g(N))下界f(N)=Ω(g(N))阶f(N)=θ(g(N))二、算法复杂性算法复杂性的分析for(inti=0;i2、intj=i;j0){//用O(1)的时间选择一个1~size范围内的值t=select(size);size-=t;for(intj=0;j3、,a,c,b);Move(n,a,c);Hanoi(n-1,b,a,c);return1;}二、算法复杂性递推方程的求解代入法:对结果式进行预测,并用数学归纳法进行证明。二、算法复杂性递推方程的求解迭代法:将递推式展开,进行级数求和。intQSort(List&L,ints,intt){if(s>=t)return1;intk=Partition(L,s,t);QSort(L,s,k-1);QSort(L,k+1,t);return1;}...二、算法复杂性递推方程的求解公式法二、算法复杂性递推方程的求解生成函数法对序列(4、a0,a1,..),定义函数:g(z)=a0+a1z+a2z2+..+anzn+..称为序列(a0,a1,..)的生成函数。利用递推公式建立关于生成函数的定解方程解定解方程得到生成函数的级数形式,其系数即为序列的解。即:Tn=2n-1kn-1-k二叉树计数问题:由n个结点可以构成多少种不同形态的二叉树?……
2、intj=i;j0){//用O(1)的时间选择一个1~size范围内的值t=select(size);size-=t;for(intj=0;j3、,a,c,b);Move(n,a,c);Hanoi(n-1,b,a,c);return1;}二、算法复杂性递推方程的求解代入法:对结果式进行预测,并用数学归纳法进行证明。二、算法复杂性递推方程的求解迭代法:将递推式展开,进行级数求和。intQSort(List&L,ints,intt){if(s>=t)return1;intk=Partition(L,s,t);QSort(L,s,k-1);QSort(L,k+1,t);return1;}...二、算法复杂性递推方程的求解公式法二、算法复杂性递推方程的求解生成函数法对序列(4、a0,a1,..),定义函数:g(z)=a0+a1z+a2z2+..+anzn+..称为序列(a0,a1,..)的生成函数。利用递推公式建立关于生成函数的定解方程解定解方程得到生成函数的级数形式,其系数即为序列的解。即:Tn=2n-1kn-1-k二叉树计数问题:由n个结点可以构成多少种不同形态的二叉树?……
3、,a,c,b);Move(n,a,c);Hanoi(n-1,b,a,c);return1;}二、算法复杂性递推方程的求解代入法:对结果式进行预测,并用数学归纳法进行证明。二、算法复杂性递推方程的求解迭代法:将递推式展开,进行级数求和。intQSort(List&L,ints,intt){if(s>=t)return1;intk=Partition(L,s,t);QSort(L,s,k-1);QSort(L,k+1,t);return1;}...二、算法复杂性递推方程的求解公式法二、算法复杂性递推方程的求解生成函数法对序列(
4、a0,a1,..),定义函数:g(z)=a0+a1z+a2z2+..+anzn+..称为序列(a0,a1,..)的生成函数。利用递推公式建立关于生成函数的定解方程解定解方程得到生成函数的级数形式,其系数即为序列的解。即:Tn=2n-1kn-1-k二叉树计数问题:由n个结点可以构成多少种不同形态的二叉树?……
此文档下载收益归作者所有