- 1、本文档共25页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第三讲 算法的复杂度分析与最优算法
Introduction to Algorithms
算法导论
李彬
山东轻工业学院 理学院
第一章 引论
算法的复杂度分析与最优算法
2
增长阶
例:
sum=0;
for(i=1;i=n;i++)
for(j=1;j=n;j++)
sum++;
3
增长阶
2
T(n)=O(n )
4
算法分析的基本法则
非递归算法:
(1)for / while 循环
循环体内计算时间*循环次数;
(2)嵌套循环
循环体内计算时间*所有循环次数;
(3)顺序语句
各语句计算时间相加;
(4 )if-else语句
if语句计算时间和else语句计算时间的较大者。
5
templateclass Type
void insertion_sort(Type *a, int n)
{
Type key; // cost times
for (int i = 1; i n; i++){ // c1 n
key=a[i]; // c2 n-1
int j=i-1; // c3 n-1
while( j=0 a[j]key ){ // c4 sum of ti
a[j+1]=a[j]; // c5 sum of (ti-1)
j--; // c6 sum og (ti-1)
}
a[j+1]=key; // c7 n-1
}
}
6
n−1 n−1 n−1
T(n) c n +c (n −1) +c (n −1) +c t +c (t −1) +c (t −1) +c (n −1)
您可能关注的文档
- 第七组-靠什么凝聚你的企业,企业文化.pdf
- 第三军医大学考试课程资料儿科.pdf
- 第七讲 昆曲 [兼容模式].pdf
- 第七讲信道编码技术(一).pdf
- 第三军医大学考试课程资料大体解剖学TK.pdf
- 第三代防盗止动器.pdf
- 第三军医大学考试课程资料妇产科.pdf
- 第七章 悬索桥施工.pdf
- 第三军医大学考试课程资料神经解剖.pdf
- 第三章 用激光的多普勒极限吸收光谱和荧光光谱学.pdf
- 5.3.1函数的单调性(教学课件)--高中数学人教A版(2019)选择性必修第二册.pptx
- 部编版道德与法治2024三年级上册 《科技提升国力》PPT课件.pptx
- 2.7.2 抛物线的几何性质(教学课件)-高中数学人教B版(2019)选择性必修第一册.pptx
- 人教部编统编版小学六年级上册道德与法治9 知法守法 依法维权(第一课时)课件.pptx
- 三年级上册品德道德与法治《学习伴我成长》.pptx
- 部编版小学道德与法治六年级上册6 人大代表为人民 课件.pptx
- 部编版小学道德与法治六年级上册1感受生活中的法律第一课时课件.pptx
- 2.5.2圆与圆的位置关系(教学课件)-高中数学人教A版(2019)选择性必修第一册.pptx
- 2.5.1直线与圆的位置关系-(教学课件)--高中数学人教A版(2019)选择性必修第一册.pptx
- 14.1.1 同底数幂的乘法(教学课件)-初中数学人教版八年级上册.pptx
文档评论(0)