科技: 人物 企业 技术 IT业 TMT
科普: 自然 科学 科幻 宇宙 科学家
通信: 历史 技术 手机 词典 3G馆
索引: 分类 推荐 专题 热点 排行榜
互联网: 广告 营销 政务 游戏 google
新媒体: 社交 博客 学者 人物 传播学
新思想: 网站 新书 新知 新词 思想家
图书馆: 文化 商业 管理 经济 期刊
网络文化: 社会 红人 黑客 治理 亚文化
创业百科: VC 词典 指南 案例 创业史
前沿科技: 清洁 绿色 纳米 生物 环保
知识产权: 盗版 共享 学人 法规 著作
用户名: 密码: 注册 忘记密码?
    创建新词条
科技百科
  • 人气指数: 6979 次
  • 编辑次数: 1 次 历史版本
  • 更新时间: 2009-03-18
admin
admin
发短消息
相关词条
数学
数学
数论
数论
工业设计
工业设计
智慧产业
智慧产业
符号位
符号位
算法设计与分析
算法设计与分析
银行家算法
银行家算法
比例计算法
比例计算法
关键路径
关键路径
先来先服务
先来先服务
推荐词条
希拉里二度竞选
希拉里二度竞选
《互联网百科系列》
《互联网百科系列》
《黑客百科》
《黑客百科》
《网络舆情百科》
《网络舆情百科》
《网络治理百科》
《网络治理百科》
《硅谷百科》
《硅谷百科》
2017年特斯拉
2017年特斯拉
MIT黑客全纪录
MIT黑客全纪录
桑达尔·皮查伊
桑达尔·皮查伊
阿里双十一成交额
阿里双十一成交额
最新词条

热门标签

微博侠 数字营销2011年度总结 政务微博元年 2011微博十大事件 美国十大创业孵化器 盘点美国导师型创业孵化器 盘点导师型创业孵化器 TechStars 智能电视大战前夜 竞争型国企 公益型国企 2011央视经济年度人物 Rhianna Pratchett 莱恩娜·普莱契 Zynga与Facebook关系 Zynga盈利危机 2010年手机社交游戏行业分析报告 游戏奖励 主流手机游戏公司运营表现 主流手机游戏公司运营对比数据 创建游戏原型 正反馈现象 易用性设计增强游戏体验 易用性设计 《The Sims Social》社交亮 心理生理学与游戏 Kixeye Storm8 Storm8公司 女性玩家营销策略 休闲游戏的创新性 游戏运营的数据分析 社交游戏分析学常见术语 游戏运营数据解析 iPad风行美国校园 iPad终结传统教科书 游戏平衡性 成长类型及情感元素 鸿蒙国际 云骗钱 2011年政务微博报告 《2011年政务微博报告》 方正产业图谱 方正改制考 通信企业属公益型国企 善用玩家作弊行为 手机游戏传播 每用户平均收入 ARPU值 ARPU 游戏授权三面观 游戏设计所运用的化学原理 iOS应用人性化界面设计原则 硬核游戏 硬核社交游戏 生物测量法研究玩家 全球移动用户 用户研究三部曲 Tagged转型故事 Tagged Instagram火爆的3大原因 全球第四大社交网络Badoo Badoo 2011年最迅猛的20大创业公司 病毒式传播功能支持的游戏设计 病毒式传播功能 美国社交游戏虚拟商品收益 Flipboard改变阅读 盘点10大最难iPhone游戏 移动应用设计7大主流趋势 成功的设计文件十个要点 游戏设计文件 应用内置付费功能 内置付费功能 IAP功能 IAP IAP模式 游戏易用性测试 生理心理游戏评估 游戏化游戏 全美社交游戏规模 美国社交游戏市场 全球平板电脑出货量 Facebook虚拟商品收益 Facebook全球广告营收 Facebook广告营收 失败游戏设计的数宗罪名 休闲游戏设计要点 玩游戏可提高认知能力 玩游戏与认知能力 全球游戏广告 独立开发者提高工作效率的100个要点 Facebook亚洲用户 免费游戏的10种创收模式 人类大脑可下载 2012年最值得期待的20位硅谷企业家 做空中概股的幕后黑手 做空中概股幕后黑手 苹果2013营收 Playfish社交游戏架构

算法设计与分析 发表评论(0) 编辑词条

目录

算法设计与分析编辑本段回目录

 

正文编辑本段回目录

  设计出高质量的算法,并研究算法所耗费的计算资源与问题规模之间的函数关系。算法设计与算法分析是不可分割的一个整体。算法分析的对象是被设计出的算法,而每一个被设计出的算法只有经过算法分析,才能评价其质量之优劣。
  计算效率是一个古老的研究课题。科学技术的发展使得计算日趋复杂,计算量越来越大,许多理论上可计算的问题,常常由于其计算量巨大布变成了现实不可计算的问题,这就产生了理论可计算而现实不可计算的矛盾。20世纪60年代以来,随着各个领域算法研究工作的发展,产生了一个崭新的研究领域,这就是算法的设计与分析。在这一方面已取巨大的进展,它的研究成果对于计算机在各个领域的应用起着重要的作用。
  基本内容  按照算法所处理的对象进行分类,算法设计与分析主要有数值算法和非数值算法两大领域。数值算法主要包括多项式计算、矩阵计算、有限域计算、数论计算等有关数值计算的算法问题。非数值算法主要包括整序搜索、几何问题的计算、离散结构的计算、模式匹配等有关非数值计算的算法问题。
  按照计算方式进行分类,则可分为串行算法和并行算法,还可以分为确定型算法、非确定型算法、交错型算法、随机型算法等(见计算复杂性理论)。
  另外,还有关于近似算法的研究。对于已经证明不存在快速算法,或者至今还未找到快速算法的问题,例如NP完全问题(见NP完全性), 与其花费大量的时间去寻找精确解,不如花费少量的时间去寻找近似解。
  基本概念  设计算法与分析算法的复杂度,都与计算模型有关,大多属于随机存取机器模型,这是一种确定型的串行计算模型。
  随机存取机器是一种理想的计算机,由一个累加器、一个存储器和一个程序组成。存储器具有无限多个寄存器,每个寄存器可以存放任意大的一个自然数。程序是由一些最基本的指令所组成的序列,这些指令通常是指包括直接寻址与间接寻址在内的加、减、乘、除、取数、存数、条件转移和停机。所有的运算和逻辑判断都在累加器中进行。
  问题的大小,也称问题的规模,通常用一个自然数作为随机存取机器输入数据量多少的度量。
  时间复杂度和空间复杂度分别表示对于规模为 n的输入问题、随机存取机器所耗费的时间与空间,它们都是 n的函数。常用的时间和空间的度量方式是均匀耗费标准:执行一条指令算作耗费一个单位的空间,使用一个寄存器算作耗费一个单位的空间;另一种度量方式是对数耗费标准(见随机存取机器模型)。复杂度函数的计算方式又有两种:规模为n的所有问题的复杂度的最大值称为最环情况复杂度;规模为n的所有问题的复杂度的平均值称为平均情况复杂度。当规模n增加时,复杂度的量级即极限属性称为渐近复杂度。由于理论计算机与现实计算机之间的差异,以及不同的现实计算机之是的差异,也由于算法设计与分析主要关心规模 n比较大的情况,通常讨论的是渐近复杂度。
  算法设计  算法设计的任务是对各类具体的问题设计高质量的算法,以及研究设计算法的一般规律和方法。常用的算法设计方法主要有分治法、动态规划、贪婪法和回溯法等。
  分治法  把一个大规模问题划分成几个子问题,对每一个子问题采用同样的处理方法,求出各子问题的解答,再把这些子问题的解答组合成整个问题的解答。
  动态规划  当整个问题的解答无法由少数几个子问题的解答组合得出,而依赖于大量子问题的解答,并且子问题的解答又需要反复利用多次时,系统地列表记录各个子问题的解答,据此求出整个问题的解答。
  贪婪法  在算法的每一步骤,都采取当前看来可行的或最优的策略。这是一种最直接的方法,只有在一些特殊情况下,贪婪法才能求出问题的解答。对于录求最优解的问题、贪婪法通常只能求出近似解。
  回溯法和分叉截断法  为了寻求问题的解答,有时需要在所有的可能性(称为候选对象)中进行系统的搜索,例如在寻求最优解的问题中,就常碰到这种情况。这时,须把各种候选对象组织成一棵树,每个树叶对应着一个候选对象,于是每个内部顶点就表示若干个候选对象(即在此顶点下面的树叶)。回溯法是从树根开始按深度优先搜索的原则向下搜索,即沿着一个方向尽量向下搜索,直到发现此方向上不可能存在解答时,就退到上一个顶点,沿另一个方向进行同样的工作。分叉截断法也是从树根开始向下搜索,不同的是,分叉截断法常常利用一个适当选取的评估函数,来决定应该从哪一点开始下一步搜索(分叉),以及哪一点下方不可能存在解答,从而这点的下方不必进行搜索(截断)。评估函数选得好,就会很快地找到解答,选得不好,就可能找不到解答或者找到的不是最优解(有时它可以作为最优解的一个近似解)。
  算法分析  对于设计出的每一个具体的算法,利用数字作为工具讨论它的各种复杂度,就是算法分析的主要任务。复杂度分析的结果可以作为评价算法质量的标准之一,有时也可以为改进算法的方向提供参考。分析算法的复杂度需要较强的数学技巧,针对不同的算法,采用不同的分析方法。
  讨论某些问题类在一定的计算模型中的任意算法的复杂度至少是多大,也是算法分析的一个内容,这就是下界问题。
  通常认为,多项式复杂度的算法是现实可行的,而指数复杂度的算法是现实不可行的。
  参考书目
 A.V.Aho,J.E.Hopcroft,J.D.Ullman,The Design and Analysis of Computer Algorithms,Addison Wesley,Reading,Mass.,1974.
 D.E.Knuth, The Art of Computer Programming,Vol.1~3,Addison Wesley,Reading,Mass.,1968~1973.

 

配图编辑本段回目录

 

相关连接编辑本段回目录

→如果您认为本词条还有待完善,请 编辑词条

词条内容仅供参考,如果您需要解决具体问题
(尤其在法律、医学等领域),建议您咨询相关领域专业人士。
0

标签: 算法设计与分析

收藏到: Favorites  

同义词: 暂无同义词

关于本词条的评论 (共0条)发表评论>>

对词条发表评论

评论长度最大为200个字符。