算法和算法复杂性1课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《算法和算法复杂性1课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 复杂性 课件
- 资源描述:
-
1、 图灵机中图灵机中无限长的带无限长的带被分成一个个小空格,被分成一个个小空格,每格容纳一个符号,对每一部图灵机而言,带上每格容纳一个符号,对每一部图灵机而言,带上允许使用的符号是有限的;允许使用的符号是有限的; 图灵机的输入图灵机的输入是由符号组成的有限序列,称是由符号组成的有限序列,称之为符号行,输入符号行不能含空格符之为符号行,输入符号行不能含空格符B。 读写头读写头每次左或右移动一格,并根据控制器每次左或右移动一格,并根据控制器的指令阅读方格中的符号或抹去、重写方格中的的指令阅读方格中的符号或抹去、重写方格中的符号,其初始位置是输入符号行最左边符号。符号,其初始位置是输入符号行最左边符号
2、。读写头读写头 带带(B B表示空格)表示空格) B 0 1 1 0 0 0 B控制器控制器 控制器控制器有有限个状态,其中启始状态和有有限个状态,其中启始状态和终止状态是两个特殊的状态;状态可依终止状态是两个特殊的状态;状态可依转移转移函数函数进行,进行,(q,a)=(p,b,v)意为:)意为:读写头看到符号读写头看到符号a时,处于状态时,处于状态q的控制器命的控制器命令其抹掉令其抹掉a,重写,重写b,并向,并向v(左或右)移动(左或右)移动一格,状态改变为一格,状态改变为p; 控制器开始处于启始状态,图灵机当且控制器开始处于启始状态,图灵机当且仅当控制器处于终止状态时停止,此时仅当控制器处
3、于终止状态时停止,此时带上带上符号行符号行为输出。为输出。 显然,图灵计算机计算的是显然,图灵计算机计算的是从符号行到符号从符号行到符号行的函数行的函数,但并不太限制其应用范围,但并不太限制其应用范围,它的它的计算计算时间时间是指读写头的移动次数是指读写头的移动次数,计算占用的空间计算占用的空间是是指带上被访问过的方格数指带上被访问过的方格数,当输入符号行是当输入符号行是x时时,图图灵机灵机M的计算时间的计算时间(或占用空间或占用空间)记为记为Time M(x) (或或Space M(x)。 图灵精彩地论证了图灵精彩地论证了 一个典型问题就是一个典型问题就是:给定给定一个带有输入的计算机程序,
4、它会停机吗?一个带有输入的计算机程序,它会停机吗?图灵证明了,不存在一个算法能对该问题的图灵证明了,不存在一个算法能对该问题的一切例子给出正确的答案。一切例子给出正确的答案。 对于给定的问题,如果对于给定的问题,如果存在一种算法,可存在一种算法,可以对该问题的一切例子给出正确的答案,那以对该问题的一切例子给出正确的答案,那麽这个问题就是麽这个问题就是的。的。 可重复性可重复性归根于归根于,这,这种确定性也是当今世界上存在的各式各样计种确定性也是当今世界上存在的各式各样计算机的共同特点。算机的共同特点。若若f(x)f(x)无定义无定义, ,则对输入则对输入x, Mx, M的任何计算的任何计算道路
5、都是道路都是( (时间时间) )无限长的无限长的; ;若若f(x)f(x)有定义有定义, ,则对输入则对输入x, Mx, M必有一有限长必有一有限长的道路;并且对任何有限长的计算道路,计的道路;并且对任何有限长的计算道路,计算结果都是算结果都是f(x)f(x)。 对这种图灵机对这种图灵机 M M,Time Time M M(x x)表示输入)表示输入x x时,时,M M可能使用的最短时间可能使用的最短时间,Space Space M M(x x)表示输入表示输入x x时,时,M M可能使用的最少空间可能使用的最少空间。可以可以在不确定型计算机上实施的计算称为在不确定型计算机上实施的计算称为。(
6、Non-deterministic computationNon-deterministic computation) 。与此有关的因素有:与此有关的因素有:一般指问题的输入长度一般指问题的输入长度为了衡量算法的效果所广泛采用的为了衡量算法的效果所广泛采用的是:是: 为了避免由于不同输入而对算法行为了避免由于不同输入而对算法行为产生巨大差别,考察所有规模为为产生巨大差别,考察所有规模为n n的的输入输入,。因此,算法复杂性是输入因此,算法复杂性是输入规模的函数,比如规模的函数,比如10n10n3 3,2,2n n,nlog,nlog2 2n n等。等。输入规模足够大时,在复杂性函数中,输入规模
7、足够大时,在复杂性函数中,较慢的项(如较慢的项(如nlognlog2 2n+5nn+5n),终将被增长),终将被增长速度很快的项超过(该例中速度很快的项超过(该例中n1000n1000时,时,nlognlog2 2n5nn5n)。)。只有规模大的输入,才能确定只有规模大的输入,才能确定。比如复杂性为。比如复杂性为10n10n3 3与复杂性为与复杂性为9n9n3 3的算的算法间的差别可以忽略不计,因为这可以通过技法间的差别可以忽略不计,因为这可以通过技术革新,使计算机速度提高术革新,使计算机速度提高1010倍而得到补偿。倍而得到补偿。(c)(c)如果存在两个常数如果存在两个常数c,c0,c,c0
8、,使得当使得当n n足够大时有足够大时有cg(n)f(n)cg(n),cg(n)f(n)cg(n),则记则记f(n)=g(n)f(n)=g(n),用记号,用记号f(n)g(n)f(n)g(n)代替代替f(n)=(g(n),f(n)=(g(n),易见易见是一个等是一个等价关系,在该等价关系下,价关系,在该等价关系下,f(n)f(n)的等价类(即的等价类(即f(n)=(g(n)f(n)=(g(n)的所有的所有g(n)g(n)的集合)称为的集合)称为 设设f(n),g(n)f(n),g(n)是定义在正整数上的正实值函数是定义在正整数上的正实值函数(a)(a)如果存在一个常数如果存在一个常数c0,c0
9、,使得当使得当n n足够大时足够大时, ,有有f(n)cg(n),f(n)cg(n),则记则记f(n)=O(g(n)f(n)=O(g(n);(b)(b)如果存在一个常数如果存在一个常数c0,c0,使得当使得当n n足够大时有足够大时有f(n)cg(n),f(n)cg(n),则记则记f(n)=(g(n)f(n)=(g(n); 算法分析中常常使用算法分析中常常使用初等运算初等运算算术算术运算、比较、转移指令等运算、比较、转移指令等的步数的步数表示一个算表示一个算法在假设的计算机上执行时所需的时间,即法在假设的计算机上执行时所需的时间,即每做一次初等运算,需要一个单位时间。而每做一次初等运算,需要一
10、个单位时间。而当把算法当把算法的输入表示为符号串时,那麽的输入表示为符号串时,那麽输入规模输入规模就定义为该符号串的长度就定义为该符号串的长度(符号串中符(符号串中符号的数目),称为号的数目),称为。例例1以某一个固定数为基底的运算系统(如十进以某一个固定数为基底的运算系统(如十进制 或 二 进 制 ) 中 , 表 示 一 个 整 数制 或 二 进 制 ) 中 , 表 示 一 个 整 数 n 的 输 入 规的 输 入 规模:模: ,因为,因为logBn=logn/logB, B固定后固定后logB是是一个常数。一个常数。nBlog例例2.试分析试分析LP的规模的规模. 设设A、b、c中的元素均
11、为整数,则中的元素均为整数,则LP的规模就的规模就是表示是表示A、b、c所需符号的数目。因为可以把二进所需符号的数目。因为可以把二进制(十进制)表示的矩阵中元素排成一行,用符号制(十进制)表示的矩阵中元素排成一行,用符号线适当地隔开以表示矩阵的行或列,从而矩阵也可线适当地隔开以表示矩阵的行或列,从而矩阵也可以表示为符号串。所以,以表示为符号串。所以,mn的的LP问题规模为问题规模为(mn+ )其中)其中p是所有非零参数的乘积。是所有非零参数的乘积。plog决定一个算法的决定一个算法的实际效用实际效用,要看其,要看其。目。目前计算机科学家们有一个公认的看法:前计算机科学家们有一个公认的看法: 设
展开阅读全文