1.4 算法与时间复杂度

视频加载中...

上一节介绍了计算机内部信息的表示，讲解了二进制程序、字符ASCII存储，对整数的原码、反码和补码，定点数和浮点数的表示和存储进行详细分析。本节介绍算法的概念、特点和评价以及时间复杂度简单分析方法。

算法是解决问题的办法或方案，是一系列步骤的有序集合。每个人每天的每一个活动都有一个算法支撑，比如起床、上课、吃饭、购物等活动，每个活动都有一些步骤。我们以“起床”活动为例看看生活中的算法：

：

以上11个步骤构成了“起床”活动，但是并不是所有人的“起床”活动的步骤和顺序都是一样的，其中有些步骤的顺序可以交换，有些则不能。同一个人在不同的季节“起床”活动的步骤也会不同。在夏天基本不用第(6)步，有些人起晚了可能(9)到(11)步都不会做，有些女生夏天不做第(7)步；第(4)(5)(8)三步不做出不了门见人。同样是“起床”，每个人执行的“算法”可能不同。想一想，超人那套服装是怎样穿上去的！

算法的一些步骤完成顺序不能颠倒，试想一下“穿内裤”“穿卫衣”“穿外衣”等三个步骤的顺序颠倒了，这个人的形象如何？而有些步骤可以交换次序，如“刷牙”“洗脸”“梳头”，因为这些步骤之间没有依赖。“算法”的每个步骤执行要遵循一定规则，同样是“穿”的动作，穿衣、穿裤和穿鞋等的是不一样的；算法的每个步骤也可能有多种选择，如“穿衣”，可能穿便装、可能穿西装、可能穿夹克，每个步骤的不同选择构成了不同个人着装风格。

我们以“起床”的日常活动来揭示了算法的一些思想。那么，什么是计算机算法？简而言之，是用计算机求解具体问题而设计的一系列有限的步骤的集合。一个计算机的算法应该具备五个特征。一是输入，计算机可以有0到多个数据的输入，没有数据输入的算法很少见，因为数据是算法处理的对象；二是输出，算法至少要有一个输出，算法本质是对数据进行处理，处理的结果应该被利用或呈现给人看，否则算法无意义；三是确定性，又称无二义性，算法的每个步骤表达的意思是一致的，所有人阅读算法得到的结果是一样的；四是可行性，算法的每个步骤计算机都应该能实现，不能实现的步骤不能出现在算法中；五是有穷性，或称有限性，无论地老天荒，算法总是要求能够执行到最后一步。