算法基本概念

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

"好”算法应该怎么样?

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

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

时间复杂度

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

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

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

求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) zcxblog.cn版权所有, 转载请说明= 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次, 对常数项运算次数, 我们得到的时间复杂度为T(n) = O(1).

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

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

延伸概念

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

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

平均时间复杂度: 所有可能情况平均下来的zcxblog.cn版权所有, 转载请说明时间复杂度.

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

空间复杂度

空间复杂度描述算法占用的储存空间, 用S(n) = O(n最大zcxblog.cn版权所有, 转载请说明数量级) = 表示, 多数情况下, 比时间复杂度更好分析. 正确的分析空间复杂度需要对各种基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).