设为首页 - 加入收藏
广告 1000x90
您的当前位置:三五图库香港35图库大全 > 不变式 > 正文

算法基础——算法导论(1)

来源:未知 编辑:admin 时间:2019-06-10

  在生活中的一个应用场景就是玩扑克时,右手(不考虑左撇子)不断从桌上拿起一张扑克,按大小插入到左手的扑克序列的相应位置中。在结束时,左手的扑克是排好序的。

  在以上程序中,每轮循环结束(外层for循环)时,a[0~i](表示a数组的0~i位)都是排好序的,我们把a[0~i]的这一性质形式地表示为一个循环不变式。

  如果循环迭代式某次迭代之前它为true,那么下次迭代之前它也为true;

  在循环终止时,不变式为我们提供一个有用的性质,该性质有助于证明算法是正确的;

  保持:假设在第i次迭代之前,不变式成立,即子数组a[0~i-1]是排好序的;在进行第i次迭代时,根据算法,a[i]从子数组a[0~i-1]的最右端不断向左移动,直到找到自己合适的位置,此时子数组由a[0~i-1]扩充为a[0~i]。因此在进行第i+1次迭代之前,子数组a[0~i]也是排好序的。

  我们假定一种通用的单处理器计算模型随机访问机(random-access machine,RAM)来作为实现技术的模型。在该模型中,一些常用的计算机指令,包括算术指令(加、减、乘、除、取余、向上取整、向下取整)、数据移动指令(装入、储存、复制)和控制指令(条件与无条件转移、子程序调用与返回),它们执行所需的时间为常量。

  做更近一步的简化抽象,我们真正感兴趣的是运算时间的增长率(增长量级)。因此忽略低阶项和最高阶项的常系数。记插入排序(insert-sort)的最佳情况运行时间为:(n),最坏情况运行时间为:(n)。

  对于插入排序(insert-sort),我们更应该考虑的是最坏情况,因为:① 最坏情况给出了一个上界,可以确保该算法不会超过某一时间;② 最坏情况往往经常出现;③ “平均情况”和最坏情况大致一样差。

  插入排序(insert-sort)采用了增量方法,将a[i]插入子数组a[0~i-1]中,子数组增长为:a[0~i]。

  下面介绍一种叫做分治法(Divide and Conquer)的设计方法:将原问题分解为几个规模较小的但类似于原问题的子问题,递归的解决这些子问题,然后合并这些子问题的解来建立原问题的解。

  设T(n)为规模为n的问题运用分治法所需的运行时间。若问题规模足够小,如对于某个常量c,n = c,则直接求解需要常量时间,记为:(1);否则,把问题分解成a个子问题,每个子问题的规模是原来的1 / b,则T(n) = a * T(n / b),如果分解为子问题所需时间为D(n) (可记为:(1)),合并子问题所需的时间为C(n)(可记为:(n)),那么T(n)递归式为:

  可见当n较大时,在最坏情况下,归并排序(merge-sort)优于插入排序(insert-sort)。

  ps:以上内容均摘自《算法导论》中文译本。本人只是提取出文中个人认为比较重要的点,加入了一些个人理解,仅供参考。有些句子和词由于是翻译过来的,所以可能比较突兀,会意就好。

本文链接:http://1763inn.com/bubianshi/874.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top