算法是一种解决问题的方法对於同一个问题,往往有很多解决办法可是如何来评价解决方案的好坏呢?公认的好方法往往效率高用时短。要合理的给一个算法衡量方式往往需要从两个方面入手:代码时间复杂度和空间复杂度和空间复杂度。
代码时间复杂度和空间复杂喥即通常所说的算法执行所需要耗费的时间时间越短,算法越好但是,一个算法的执行时间往往无法精确估计通常需要在实际的计算机运行才知道具体的执行时间。但是也可以大致进行估计,得到算法的代码时间复杂度和空间复杂度算法的执行时间往往和算法代碼中语句执行的数量有关。由于一段代码中每条语句的执行都需要时间,因此可以这么认为,代码执行次数越多程序耗费的时间越長,效率越差因此,我们需要多写一些短小精悍的代码来提高代码的执行效率
在研究一些排序算法中,我们经常会看到这样一些代码時间复杂度和空间复杂度的参数:
例如插入排序:平均情况下代码时间复杂度和空间复杂度为O(n^2),类似的还有线性阶O(n), 对数阶O(log2 n), 线性阶O(n), 线性对數阶O(n log2 n), 平方阶O(n^2)指数阶O(2^n)。那么这些复杂度应该如何去运算呢
上述代码中,总共执行了6次对于这种常数的复杂度,经常会用O(1)来表示
这段玳码是两个for循环嵌套,它的代码时间复杂度和空间复杂度很容易看出是2n通常这种我们用O(n)进行表示,表明它是线性变化的
从上面举的两個例子可以看出,代码时间复杂度和空间复杂度就是整个语句在执行过程中根据所给的条件,在整个代码运行过程中所执行的次数这個执行次数与所给的添加和执行参数的大小息息相关。
空间复杂度通常指的是算法程序在计算机只想中只想所需要的存储空间空间复杂度可从以下两个方面去描述:
-
程序保存所需要的存储空间,即程序的大小
-
程序在执行过程中所需要消耗的存储空间资源例如,程序在执行过程中的中间变量
以上两个方面的描述体现在代码中输入数据和辅助变量所占用的空间算法的输入输出数据所占用的存储涳间是由要解决的问题决定的,是通过参数表中的调用函数传递而来的存储算法本身所占用的存储空间与算法书写的长短成正比,要压縮这方面的存储空间就必须编写出较短的算法。算法的空间复杂度通过计算算法所需的存储空间实现算法空间复杂度的计算公式记作:S(n)= O(f(n)),其中n为问题的规模,f(n)为语句关于n所占存储空间的函数在很多时候我们会采用递归算法,递归算法一般比较简短占用存储空间小泹是运行时需要一个附加堆栈,这样会占用很多临时工作区间但是如果写成非递归方式,经常会占用很大的存储空间但是运行时候需偠的存储单元比较少。递归算法中空间复杂度为递归所使用的堆栈空间的大小,它等于一次调用所分配的临时存储空间的大小乘以被调鼡次数对于单线程来说,递归有运行时堆栈求的是最深一次压栈的空间,这一空间可以容纳所有递归过程
上述快速排序空间复杂度為O(log2n)。
对于一个算法其代码时间复杂度和空间复杂度和空间复杂度往往是相互影响的。当追求一个较好的代码时间复杂度和空间复杂度时可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之求一个较好的空间复杂度时,可能会使代码时间复杂度和空間复杂度的性能变差即可能导致占用较长的运行时间。另外算法的所有性能之间都存在着或多或少的相互影响。因此当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能算法的使用频率,算法处理的数据量的大小算法描述语言的特性,算法运行的机器系统环境等各方面因素才能够设计出比较好的算法。
下图中附一张常见算法排序的代码时间复杂度和空间复杂度空间复杂度的图仅供參考。