算法概念简介-计算机基础

日常生活中，使用计算机处理各种不同的问题，首先要对各类问题进行分析，确定解决问题的方法和步骤，再编好一组让计算机执行的指令即程序，最后交给计算机，然后计算机按照人们制定的步骤有效地工作。这些具体的方法和步骤，实质就是解决一个问题的算法。

1.算法的定义

广义的算法是指为完成某项工作的方法和步骤。算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。狭义的算法是为解决一个问题而采取的方法和步骤。

2.算法的基本特征

一个算法应该具有以下五个重要的特征：

（1）有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限次数步骤之后终止。

（2）确切性（Definiteness）：算法的每一步骤必须有确切的定义。

（3）输入项（Input）：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。

（4）输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

（5）可行性（Effectiveness）：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称为有效性）。

3.算法的评价

对于相同的问题，可以采用不同的算法去解决，不同的算法从质量上来说必然是不同的，一个算法的质量优劣将直接影响程序的效率，哪一种算法更好是非常有必要去评价一下。那么在确保算法正确性的前提下，评价一个算法主要有两个指标：时间复杂度和空间复杂度。(https://www.xing528.com)

（1）时间复杂度。

一般情况下，算法中基本操作重复执行的次数是问题规模n的一个函数f（n），算法的时间度量记作T（n）＝O（f（n）），它表示随着问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称为算法的渐近时间复杂度，简称时间复杂度。所以，时间复杂度定义为：算法中的基本操作的执行次数。

观察下面代码，计算一下fun的基本操作执行了多少次？

对于fun函数来说，基本操作的执行次数为：f（n）＝n2＋2n＋10；则fun函数的时间复杂度为：f（n）＝n2＋2n＋10。

时间复杂度和实际运行时间不是一码事，我们在计算时间复杂度的时候，是忽略所有低次幂和最高次幂的系数的。

比如有一个算法，输入n个数据，经过次计算得到结果，其时间复杂度为O（n2）。另外一个算法只需2n2次计算就能得到结果，其时间复杂度也是O（n2），但明显比第一个算法要快。

所以说时间复杂度是可以推演计算的，而实际运算时间不可预测。这也是为什么使用时间复杂度而不是使用实际运算时间来判断一个算法的优劣了。

（2）空间复杂度。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记作S（n）＝O（f（n））。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。所以，空间复杂度定义为：算法中变量的个数。

Fibonacci函数中的变量有：n、i、fibArray以及fibArray所指向的n＋1个空间，所有该算法中共有n＋4个变量，故空间复杂度为O（n）。