理工酷

算法评价

对于一个算法的评价，通常要从正确性、可理解性、健壮性、时间复杂度以及空间复杂度等多个方面加以衡量。相比而言，人们更关心的是计算机系统资源密切相关的时间复杂度和空间复杂度。 对于求解的问题，通常会有多种不同的算法。虽然这些算法都是正确的，都能得到期望的结果，但是，不同的算法在获得这些结果时消耗的资源确实不同的。执行算法时所消耗资源的多少称为算法的效率。

算法的时间复杂度

时间复杂度用来度量时间的复杂性，即算法的时间效率的指标。换言之，时间复杂度时与求解问题规模、算法输入数据相关的函数，该函数表示算法运行所花费的时间。为了简化问题，通常用算法运行某段核心代码的次数来代替准确的执行时间，记为T(n)，其中，n代表求解问题的规模，一般是指待处理数据量的大小。 在实际问题的时间复杂度分析中，经常考虑的时当问题规模趋近于无穷大的情形，因此引入符号O，以此简化时间复杂度T(n)与求解问题规模n之间的函数关系，兼具啊后的关系时一种数量级关系。例如，如果某个算法的时间复杂度为T(n)=n^2+2n，那么当求解问题规模趋近于无穷大时，有T(n)/ n^2趋近于1，表示算法的时间复杂度与n^2成正比。 时间复杂度最好的算法是常数数量级算法。常数数量级算法的运行时间是一个常数，算法所消耗的时间不随所处理的数据个数n增大而增大。或者说，常数数量级算法和所处理的数据个数n无关，表示为O(c)，其中c表示任意常数。

算法的空间复杂度

算法的空间复杂度是度量空间的复杂性，即执行算法的程序在计算机中运行时所占用空间的大小。换言之，空间复杂度也是与求解问题的规模、算法出入数据相关的函数，记为S(n)，其中，n代表求解问题的规模。 空间复杂度主要也是考虑当前问题规模趋近于无穷大的情形，空间复杂度的分析方法与时间复杂度也是类似的，往往希望算法有常数数量级或或多项式数量级的空间复杂度。 随着计算机硬件的发展，对于算法的空间复杂度的要求逐渐下降，时间复杂度相对来说变得更加重要。