人工智能算法(Python语言版)PPT第1章_算法设计与分析基础.pptx
《人工智能算法(Python语言版)PPT第1章_算法设计与分析基础.pptx》由会员分享,可在线阅读,更多相关《人工智能算法(Python语言版)PPT第1章_算法设计与分析基础.pptx(27页珍藏版)》请在三一文库上搜索。
1、提纲w 概述w 算法的基本概念w 算法效率分析w 算法的最优、最坏和平均效率w 算法运行时间估计w 总结概述(1)w 人工智能的三大基石:人工智能的三大基石:数据,算法,算力;人工智能的本质是算法;算法的优劣决定了智能系统水平高低w 算法对工程教育毕业要求的支撑:算法对工程教育毕业要求的支撑:-工程知识:工程知识:能够将数学、自然科学、工程基础和专业知识用于解决计算机领域的复杂工程问题。-设计设计/开发解决方案:开发解决方案:能够设计针对复杂工程问题的解决方案,设计满 足特定需求的软件系统、模块/组件,并能够在设计环节中体现创新意识,考虑社会、健康、安全、法律、文化以及环境等因素。-研究:研究
2、:能够基于计算机科学与工程的技术和方法对复杂工程问题进行分析与研究,包括设计实验、分析与解释数据、并通过信息综合得到合理有效的结论。概述(2)w 学界与业界为实现同样的目标而努力w 人们越来越客观地看待学界与业界研究工作的价值,学界与业界的对立逐渐消除、逐渐认可对方的价值w 计算机科学的特点需要业界做科研、学界解决实际问题,算法助力克服技术瓶颈w学界与业界的合作成为常态,算法的价值得到双方认可当代计算机专业人才工程能力 算法“驾驶员”+“算法造车人”算法设计与分析助力程序设计能力的提升、程序设计水平的提高程序设计能力提升算法设计与分析水平提纲w 概述w 算法的基本概念w 算法效率分析w 算法的
3、最优、最坏和平均效率w 算法运行时间估计w 总结算法的基本概念(1)l算法:算法:解决问题的一步一步的方法l数据结构数据结构+算法算法=程序程序 -有了好的算法和数据结构,以某种程序设计语言予以实现 -算法不依赖于特定程序语言,描述求解问题的通用的一般步骤l算法的定义与特点算法的定义与特点 算法是一系列解决问题的步骤;对于符合一定规范或约束的输入,能在有限时间内得到所要求的输出;用伪代码(Pseudocode)描述;特点:(1)有穷性:)有穷性:算法在有限时间内完成。(2)确定性:)确定性:算法的每一步必须是确定的,不能有二义性的解释。(3)可行性:)可行性:算法中的每一步必须是有意义的,且能
4、达到预期目的。(4)输入:)输入:输入的值域必须仔细定义。(5)输出:)输出:得到问题的解。(6)同一问题可能存在几种不同的算法,执行效率也会有所差异。算法的基本概念(2)算法的伪代码描述示例提纲w 概述w 算法的基本概念w 算法效率分析w 算法的最优、最坏和平均效率w 算法运行时间估计w 总结算法效率分析(1)w 效率:运行时间,存储空间效率:运行时间,存储空间w 计算时间计算时间 -将操作的执行次数作为计算复杂度 -不依赖于程序运行软硬件环境和编程语言等因素且具有一般性的算法效率分析结果 -并不是实际执行的分和秒之类的时间(对于相同的运行环境有意义,但在不同处理器和内存等环境下并无意义)w
5、 增长率增长率 -基本操作:基本操作:算法中最重要(对算法运行时间的贡献最大)的操作 -关注:关注:随着输入规模的增加,算法执行时间变化的趋势 -讨论:讨论:针对较大规模的输入,运行时间的增长率或增长的阶(Order)基于渐进时间(增长率)对算法进行比较和分组算法效率分析(2)小规模输入会掩盖算法效率的显著差异,因此需要考虑大规模输入小规模输入会掩盖算法效率的显著差异,因此需要考虑大规模输入020406080100120140160180200261014182226303438x2/83*x2x+102*log x算法效率分析(3)w 2类重要操作类重要操作-比较操作(Comparison)
6、计算从数值计算发展到数据处理,比较是数据处理中最重要的操作之一 (1)所有元素比较操作等价 (2)搜索和排序算法中的基本操作-算术操作(Arithmetic)(1)加法操作(additive):+,递增(increment),递减(decrement)(2)乘法操作(multiplication):,取模(modulus)(3)算法分析中,加法操作和乘法操作分别考虑算法效率分析(4)u如何计算增长率?如何计算增长率?算法运行的渐进时间:去除了低阶项和首项系数后的算法运行时间函数,用渐进时间来表示算法的时间复杂度 对规模为n的输入,若算法运行时间为cn2,随着n的增大,正常量c的作用逐渐降低;当
7、与其他运行时间为dn3的算法相比,常量c并没有多大作用 若算法运行时间为n2logn+3n2+5n,n越大,低阶项3n2+5n对算法效率影响越小 以上算法的运行时间是n2阶、n3阶和n2logn阶的u哪几类常见的增长率?哪几类常见的增长率?多项式函数多项式函数(运行时间随着问题规模n的增加呈多项式增长)指数函数指数函数(运行时间随着问题规模n的增加而爆炸性增长,例如2n)-logn、n、n2和n3,分别称为对数函数、线性函数、平方函数和立方函数-nc和nclogn(0c1)称为次线性函数,nlogn和n1.5称为次平方函数算法效率分析(5)w 渐进时间的符号渐进时间的符号(1)符号(符号(Bi
8、g Omega)-(f):增长至少与f一样快的函数(增长不比增长不比f慢,效率不比慢,效率不比f对应算法高对应算法高)-描述了一个运行时间的下界令f(n)和g(n)是从自然数集到非负实数集的两个函数,若存在一个自然数n0和一个正常数c,使得对所有的nn0,f(n)cg(n),则称f(n)为(g(n),记为f(n)(g(n)或f(n)=(g(n)。算法效率分析(6)(2)O 符号(符号(Big Oh)-O(f):增长不比f快的函数(增长不比(增长不比f快,效率不比快,效率不比f对应算法低)对应算法低)令f(n)和g(n)是从自然数集到非负实数集的两个函数,若存在一个自然数n0和一个正常数c,使得
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 算法 Python 语言版 PPT 设计 分析 基础
链接地址:https://www.31doc.com/p-21712652.html