软件开发工程师知识整理（算法）

1.2 算法

算法：算法是为了解决某类问题而规定的一个有限长的操作序列。

1.2.1 一个算法必须满足以下五个重要特性

1. 有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
2. 确定性。对千每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，使算法的执行者或阅读者都能明确其含义及如何执行。
3. 可行性。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
4. 输入。一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
5. 输出。一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

1.2.2 评价算法优劣的基本标准

1. 正确性。在合理的数据输入下，能够在有限的运行时间内得到正确的结果。
2. 可读性。一个好的算法，首先应便于人们理解和相互交流， 其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易千隐藏错误，且难千调试和修改。
3. 健壮性。当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
4. 高效性。高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

1.2.3 时间复杂度

问题规模：问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。

语句频度：一条语句的重复执行次数。

时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

时间复杂度比较

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

常见算法的时间复杂度

1.2.4 空间复杂度

空间复杂度：指算法在计算机内执行时所需存储空间的度量。

记作：S(n)=O(f(n))

算法执行期间所需要的存储空间包括3个部分：

• 算法程序所占的空间；
• 输入的初始数据所占的存储空间；
• 算法执行过程中所需要的额外空间。

在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。