算法的描述与分析

著名的随时计算机科学家沃思教授曾提出：算法+数据结构=程序，指出了数据结构与算法在计算机科学中的地位，同时也指出了算法与数据结构的密切关系。

在用计算机解决实际问题的过程中，数据结构与算法是相辅相成、缺一不可的两个方面：数据结构是算法处理的对象，也是设计算法的基础，一个具体问题的数据在计算机中往往可以采用多种不同的数据结构来表示；另一方面，一个实际问题的计算过程常常有多种可用的算法。因此，选择什么样的数据结构和算法就成为实现应用程序过程中最重要的一个课题。

研究数据结构的目的在于更好的进行程序设计，而程序设计离不开数据的运算，运算的过程称为算法。

算法的描述

算法是对问题求解步骤的一种描述。一个算法就是一种解题的方法。严格地说，算法是由若干条指令组成的有穷序列，其中每条指令表示一个或者多个操作。

算法必须满足以下五个准则：

• 1.输入。算法开始前必须给算法中用到的变量初始化，一个算法的输入可以包含零个或多个数据。
• 2.输出。算法至少有一个或者多个输出。
• 3.有穷性。算法中每一条指令的执行次数都是有限的，而且每一步都在有穷时间内完成，即算法必须在执行优先步骤后结束。
• 4.确定性。算法中每一条指令的含义都必须明确，无二义性。
• 5.可行性。算法是可行的，即算法中描述的操作都可以通过有限次的基本运算来实现。

显然，一个程序如果对任何输入都不会陷入无限循环，则它就是一个算法。

算法分析

求解一个问题可能有多种不同的算法，而算法的好坏直接影响程序的执行效率，且不同算法之间的运行效率相差巨大。

那么，如何评价算法的优劣呢？应主要考虑以下几点：

• 1.执行算法所耗费的时间，即时间复杂度
• 2.执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性。
• 3.算法应易于理解、易于编程、易于调试等，即可读性和可操作性。

其中最主要得就是时间复杂性。一个算法所耗费得时间应该时算法中每条语句得执行时间之和，而每条语句得执行时间就是该语句得执行次数与该语句执行一次所需时间得乘积。

一般情况下，将算法所要求解得输入量称为问题得规模，并用一个正整数n来表示,算法中基本操作重复执行得次数是问题规模n得某个函数f(n)，算法得时间量度记为：T(n)=O(f(n))。

一个算法的时间复杂度（时间复杂性）T(n)就是该算法的时间耗费，它是该算法所求问题规模n的函数。当问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级(阶)称为算法的渐近时间复杂度。

随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，其中f(n)一般为算法中频度最大的语句频度。

在分析算法时，通常对算法的时间复杂度和渐近时间复杂度不作区分，经常将渐近时间复杂度T(n)=O(f(n))称为时间复杂度。

如果一个算法的执行时间是一个与问题规模n无关的常数，即使是一个较大的常数，该算法的时间复杂度都为常数阶，记作T(n)=O(1)。

算法的时间复杂度通常具有O(1)、O(n)、O(log2n)、O(nlog2n)、O(n2)、O(n3)、O(2n)和O(n!)等形式。按数量级递增排列，依次为：常数阶，对数阶，线性阶，线性对数阶，平方阶，立方阶，k次方阶，指数阶和阶乘阶。

类似于时间复杂度，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是对一个算法在运行过程中临时占用空间大小的度量，是问题规模n的函数。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法输入输出数据所占用的存储空间和算法在运行过程中临时占用存储空间这三个方面。

文章作者ianzhi,原文地址：https://cloud.tencent.com/developer/article/1476890

文章版权归作者所有，转载请保留此声明。