出来混迟早是要还的:算法技术债

287 阅读9分钟

什么是算法

百度百科是这么解释的:
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。

说人话就是能够解决问题并得出正确结果的描述。

算法的衡量标准

俗话说的好,条条大路通罗马,同一个问题的解决方法往往也不止一个,即同一个问题也可用不同的算法解决,不同的算法有优劣之分,就像你寄快递一样,有四通一达、顺丰、京东、百世等快递公司可选,不同的快递公司送货速度往往也各不相同,站在消费者的立场,快递当然是越快越好。算法也是一样,一个算法的好坏将影响到算法乃至程序的效率。衡量一个算法的优劣主要考虑两方面:时间复杂度空间复杂度

时间复杂度

时间复杂度是用来衡量一个算法耗费时间多少的标准。通常来讲,一个算法需要消耗多少时长,如果不是实际上机测试,是无法得知该算法花费的时间的,所以我们这里假设所有算法中的每条语句所消耗的时间是恒定不变的,算法中语句的执行次数越多,消耗的时间就越多。

在计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间,通过时间复杂度,人们能够对执行该算法需要的计算工作量有个大致的了解。

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得T(n)/f(n)的极限值(当n趋近于无穷大时)为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。这种表示方法被称为“大O表示法”。

计算时间复杂度

首先明确一点,这里的时间复杂度指的是最坏情况下的时间复杂度。
举个例子:
现在有十把钥匙和一把锁,已知这十把钥匙中只有一把能打开这个锁,如果要正确找到这把钥匙,我们只能一个一个去尝试开锁,知道打开这把锁。最好的结果就是第一次尝试时就打开了锁,最坏的情况是直到第十次才打开了锁。那应该使用哪种情况计算时间复杂度呢?
我们知道,算法是为了解决实际问题的,如果评价算法只考虑最优情况一定是会出现各种意外情况发生的,而且大多数情况下,最坏情况更接近平均情况,所以一般我们说时间复杂度往往指的是最坏情况的时间复杂度。
在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出 T(n) 的同数量级(它的同数量级有以下:1,log2n,n,n log2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n) = 该数量级,若 T(n)/f(n) 求极限可得到一常数c,则时间复杂度T(n) = O(f(n))。

算法的基本操作包括
1.算术运算:加减乘除等运算
2.逻辑运算:或、且、非等运算
3.关系运算:大于、小于、等于、不等于等运算
4.数据传输:输入、输出、赋值等运算

按数量级递增排列,常见的时间复杂度有:

  • 常数阶;O(1)
  • 对数阶:O(log2n)
  • 线性阶:O(n)
  • 线性对数阶:O(nlog2n)
  • 平方阶:O(n^2)
  • 立方阶:O(n^3)
  • k次方阶:O(n^k)
  • 指数阶:O(2^n)

随着问题规模n的不断增大,上述时间复杂度不断增大,换句话来说就是算法的执行效率越低。

talk is cheap

按照惯例举个例子(以leetCode题库中的第一道两数之和为例):

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i< nums.size(); i++){
            // 该步骤属于基本操作操作执行次数:n
            int current = nums[i];
            for(int j = i+1; j < nums.size(); j++){
                // 该步骤属于基本操作执行次数:n的平方次
                if(current + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
    }
    return new IllegalArgumentException("no result");
}

时间复杂度:
对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)。
关于其他模型的时间复杂度,可以参考知乎热门回答如何理解算法时间复杂度的表示法,例如 O(n²)、O(n)、O(1)、O(nlogn) 等?
我这里就不班门弄斧了~

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
类似于上文对时间复杂度的讨论,一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地”进行的,是节省存储的算法,有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。
分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说,一般都比较简短,算法本身所占用的存储空间较少,但运行时需要一个附加堆栈,从而占用较多的临时工作单元;若写成非递归算法,一般可能比较长,算法本身占用的存储空间较多,但运行时将可能需要较少的存储单元。 一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为 递归算法,其空间复杂度为递归所使用的堆栈空间的大小,它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n);当一个算法的空间复杂度与n成线性比例关系时,可表示为O(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

总结

对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。还拿上文中的寄快递举例:我们都知道顺丰快递比其他快递速度要快,但是我们寄快递也不会非顺丰不可,原因就在于顺丰虽然速度快,但是相应的价格会比其他快递高,所以当所寄物品的时效性没有那么高的时候,我们往往会选择其他快递。算法也是一样,当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。在日常开发设计算法时(特别是较为复杂的算法),要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。