《算法》世界一

一.什么是算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。一个算法必须具有：有穷性、确切性、输入项、输出项、可行性五个性质。

算法(algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

二.算法的复杂性

算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高;反之，所需的资源越低，则该算法的复杂性越低。

算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用 N、I 和 A 表示算法要解问题的规模、算法的输入和算法本身，而且用 C 表示复杂性，那么，应该有 C=F(N,I,A)。

一般把时间复杂性和空间复杂性分开，并分别用 T 和 S 来表示，则有: T=T(N,I)和 S=S(N,I) 。

搜索发现

什么是算法的复杂性

算法的复杂性主要包括两个内容:时间复杂度和空间复杂度；

（1）时间复杂度：表示算法运行时间的长短，主要和数据的规模、算法实现的效率有关，一般用 O(n)来表示，n 表示数据的规模大小。

（2）空间复杂度，主要是指算法实现所需占用内存空间的大小，一般用 S（n)来表示。

三.算法的五个特征

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

有穷性

（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止

确切性

(Definiteness)

算法的每一步骤必须有确切的定义

输入项

(Input)

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

输出项

(Output)

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

可行性

(Effectiveness)

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

四“好”算法的标准

1.正确性：正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期。

2.易读性：算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改。

3.健壮性：算法对非法数据及操作有较好的反应和处理。例如，在学生信息管理系统中登记学生年龄时，若将 21 岁误输入为 210 岁，则系统应该有错误提示。

4.高效性：高效性是指算法运行效率高，即算法运行所消耗的时间短。

5.低存储性：低存储性是指算法所需的存储空间小。对于像手机、平板电脑这样的嵌入式设备，算法如果占用空间过大，则无法运行。算法占用的空间大小被称为空间复杂度。

五.时间复杂性

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

算法的复杂度

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）

六.空间复杂性

程序的空间复杂性(space complexity)是指运行完一个程序所需要的内存大小，是计算机算法分析的重要概念之一，可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。

1.什么是空间复杂性

算法占用空间的大小

一般情况下，一个算法所占用的存储空间包括算法自身、算法的输入、算法的输出及实现算法的在程序运行时所占用空间的总和。