算法基本概念

算法(Algorithm), 说白了, 就是用计算机能理解的语言解决现实中的问题. 数据结构都整理好了, 该做的处理增删改查也有了, 剩下怎么处理大多就是算法的活了. 数据结构就是要处理的信息, 算法是处理信息的手段.

"好”算法应该怎么样?

就像现实生活中的各种“窍门”一样, 好算法的特征非常明显: 能正确(正确性), 高效(高效性), 万无一失(能处理一些异常者状况), 简单(通俗易懂)的处理问题.

就高效而言, 主要有两大衡量指标, 即时间复杂度和空间复杂度. 但不止这两个因素, 我在CSAPP中学到, 对程序局部性的高zcxblog.cn版权所有, 转载请说明效应用可以大幅提高程序的运行效率, 这涉及到其他方面的知识, 这里不在赘述.

时间复杂度

单纯用运行时间衡量算法是不可行的, 因为算法的运行时间收到太多因素的影响, 不同计算机, 甚至同一个计算机的不同时间运行同一个算法, 时间都是不同的.

如果把时间复杂度看作一个函数, 那么最根本zcxblog.cn版权所有, 转载请说明的影响因素就是数据规模n. 这好理解, 数据越多, 运行时间越长嘛. 那么, 时间复杂度的函数就是T(n), T代表Time.

T(n)的值和算法执行运算的个数有关, 加减乘除赋值都算一次运算. 同时, 又因为算法的性能只有在数据量足够大的时才会产生明显差距, 而影响最大的是来自n的最大数量级, 所以一般算法复杂度都是用T(n) = O(n最大数量级)来表示. 下面举个例子

求1到n之间所有值的和

算法1

 int sum(int end) {
     int sum = 0;                            // 运算一次
     for (int i = 1; i <= end; i++) {        // 运算n次
         sum += i;
     }
 ​
     return sum;
 }

算法1一共运算了n+1次, 即T(n) = n + 1, 只取最大数量级且去掉常数项, 我们得到的算法复杂度为 T(n) = O(n).

• 如果T(n) = 2n + 1, 那么算法复杂度为 O(n), 而不是O(2n).
• 如果T(n) = n +2n + 1, 那么算法复杂度为O(n), 而不是O(n + n).

算法2

 int sum(int start, int end) {
     int sum = 0;                        // 运算一次
 ​
     sum += end * (end + 1) / 2;         // 运算四次
 ​
     return sum;
 }

算法2移动运算了4次, 对常数项运算次数, 我们得到的时间复杂度zcxblog.cn版权所有, 转载请说明为T(n) = O(1).

同样是解决了一个问题, 算法2就比算法1在时间上更加的高效, 因为算法2的时间复杂度更低.

但很多时候, 我们直到程序运行结束后才知到算法运行的次数, 比如查找, 不确定在第几次运算后就查找到了对应元素. 这时需要引入一些延伸概念.

延伸概念

最好时间复杂度: 在所有可能情况中最低的时间复杂度.

最坏时间复杂度: 在所有可能情况中最高的时间复杂zcxblog.cn版权所有, 转载请说明度.

平均时间复杂度: 所有可能情况平均下来的时间复杂度.

在这三者中, 我们分析算法性能的指标主要是最坏时间复杂度和平均时间复杂度.

空间复杂度

空间复杂度描述算法占用的储存空间, 用S(n) = O(n最大数量级) = 表示, 多数情况下zcxblog.cn版权所有, 转载请说明, 比时间复杂度更好分析. 正确的分析空间复杂度需要对各种基本数据结构的物理结构有所了解.

数组

void test(int &n) {
     int flag[n];        // 占用空间为 4 * n 字节
     int array[n][n];    // 占用空间为 4 * n * n 字节
     int i = 0, j = 0;   // 占用空间为 4 * 2 字节
     
     for (; i < n; i++) {
         flag[i] = 0;
         for (; j < n; j++) {
             flag[i] += array[i][j];
         }
     } 
 }

和时间复杂度的分析方法一样, 这个算法的空间复杂度 S(n) = O(n).