我们为什么要研究算法？ 假设计算机是无限快的并且计算机储存器是免费的，那我们没有什么理由去研究算法，如果计算机无限快，那么用于求解某个问题的任何正确的方法都行。 然而，计算机也许是快的，但是它们不是无限快。储存器也许是廉价的，但不是免费的。所以计算时间是一种有限的资源，储存器的空间也一样。我们应当理性的运用这些资源，在时间或空间方面有效的算法将帮助你这样使用资源。 插入排序 我们第一个介绍的是插入排序，何为插入排序，我们以扑克牌为例来介绍。 假设我们手里有一套牌，并且是按着从大到小或者从小到大的顺序排列的，当我们再得到一张牌的时候，假如我们还想让这些牌是按顺序排列，那我们可以利用插入排序，让这张牌按着从左到右或者从右到左的顺序挨个和每张牌比较，如果它大于第i张牌，小于第i 1张牌，那么我们就可以把它放在第i 1的位置，然后原来的第i 1张牌到了第i 2个位置，其后的牌依次顺延。 循环不变式：每次循环从数组A中取出第j个元素插入有序区A[1 .. j-1]，然后递增j。这样A[1 ..j-1]的有序性始终得到保持，这就是所谓的"循环不变 (loop invariant)"了。不过我们必须证明这三条性质： 1，初始化：循环第一次迭代之前，它为真。 2，保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。 3，终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。 如果为了更好的理解第一二条，我们不妨类比数学归纳法。我们为了证明某条性质立，需要证明一个基本情况和一个归纳步。而第三条，不同于数学归纳法，但也许是最重要的。我们利用数学归纳法是为了证明无论n取什么值，它都是成立的，而我们的终止性是让循环终止的，我们的循环不是无限进行的，当它满足我们所需条件的时候，我们需要让它停止“归纳”。 我们就来用循环不变式来证明一下插入排序的正确性： 1，初始化：首先证明当j=2的时候，循环不等式成立。当j=2，那A=[1]，只有一个元素，一个元素默认为排序好的，成立。 2，保持：当本来A=【1，2，3……j-1】时，我们插入第j个数J，暂时A[j]=J，然后让它依次与A[j-1]，A[j-2]等等比较，如果A[j-1]大，则A[j]与A[j-1]换位置，此时A[j-1]=J，我们就可以这样依次比较下去，直到将J这个数插入到正确合适的位置，这样A[1,2,3,4,5……j]就是按着从小到大顺序排序的好的序列。 3，终止：我们的循环需要设置终止条件，假设我们希望把a个数排序好，这样，当列表（或者说数组）的元素个数大于a即可停止，当然，停止循环的条件因需要不同而不同。而且我们可以保证循环终止的时候，元素是按着顺序排列好的。 伪代码的一些约定： 1，缩进表示块结构。 2，While，for与repeat-until等循环结构以及if-else等条件结构与C,C ,Java，Python和Pascal中那些结构具有类似的解释。不像C ，Java和Pascal中的情况，伪代码退出循环后，循环计数器保持其值。因此，紧接一个For循环后，循环计数器的值就是第一个超出for循环界限的那个值。 3，符号“//”表示改行后面是注解 4，形如i=j=e的多重赋值将表达式e的值赋给变量i和j；它应被处理成等价于赋值j=e后跟着赋值i=j。 5，变量是局部于给定过程。若无显式说明，我们不使用全局变量。 6，数组元素通过“数组名【下标】”这样的形式来访问。例如A[i]表示数组A的第i个元素。 7，复合数据通常被组织成对象，对象又由属性组成。我们使用许多面向对象编程语言中创建的句法来访问特定的属性：对象名后跟一个点再跟属性名。例如，数组可以看成是一个对象，它具有属性length，表示数组包含多少元素，如A.length就表示数组A中元素个数。 我们把表示一个数组或者对象的变量看做指向表示数组或对象的数据的一个指针对于某个对象x的所有属性f，赋值y=x导致y.f=x.f。换句话说，在赋值y=x后，x和y指向相同对象。 我们的属性记号可以“串联”。例如，假设属性f本身是指向某种类型的具有属性g的对象的一个指针。那么x.f..g被隐含的加括号成（x.f）.g。换句话说，如果已经赋值y=x.f,那么x.f.g与y.g相同。 有时，一个指针根本不指向对象。这时，我们赋给他特殊值NIL。 8，我们按值把参数传递给过程：被调用过程接收其参数自身的副本。例如，如果x是某个被调用过程的参数x=y对调用过程是不可见的。然而，赋值x.f=3却是可见的。类似地，数组通过指针来传递，结果指向数组的一个指针被传递，而不是整个数组，单个数组元素改变调用过程是可见的。 9，一个return语句立即将控制返回到调用过程的调用点。大多数return语句也将一个值传递回调用者。我们伪代码与许多编程语言不同，因为我们允许在单一的return语句返回多个值。 10，布尔运算式“and”和“or”都是短路的。也就是说，当求“x and y”时，首先求x，如果x求得为FALSE，不会继续求y。如果x求值为TRUE，那么就必须求Y以确定整个表达式的值。类似地，对于表达式“x or y”，当x求值为FALSE时，才求y。 11，关键词error表示因为已经被调用过程情况不对而出现了一个错误。调用过程负责处理该错误，所以我们不用说明将采取什么行动。 本文仅仅代表个人观点~ 本文转载于微信公众号: 北航大学生科协(buaasast)，更多微信文章请扫描关注公众号: |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
