October 11, 2018 · 数据结构与算法 本文字数: 1.4k 阅读时长:5 min 全站字数:344.2k

敏而好学之WHAT——如何衡量数据结构与算法的效率

  1. 1 事前——理论分析法
    1. 1.1 渐进时间复杂度分析
    2. 1.2 渐进空间复杂度分析
    3. 1.3 最好、最坏和平均情况
    4. 1.4 均摊复杂度
  2. 2 事后统计测试分析法

本文是数据结构与算法之美专栏的学习笔记。

在继续学习各种具体的数据结构和算法之前,我们需要首先知道如何去评价不同的数据结构和算法,即分析数据结构的存储效率和算法的执行效率。

1 事前——理论分析法

所谓理论分析就是不依赖于具体的环境,如操作系统,软硬件,通过抽象算法的每一行代码的所包含的CPU指令都为一个时间单位,包含读,计算,写三个步骤。忽略每条指令在CPU上执行的时间或者在内存中占用的空间差异,统一抽象为一个基本单位的计算或者存储。

1.1 渐进时间复杂度分析

算法的执行总时间可以使用大O的渐进时间复杂度表示法,即T(n)=O(f(n)),其中n表示算法输入的数据规模的大小。f(n)表示每行代码执行的次数总和。而大O表示T(n)和f(n)是正比的关系。

T(n)=O(f(n))表示随着输入数据规模n的变化,算法的执行总时间的变化趋势,即渐进实现复杂度中渐进儿子的含义。

渐进复杂度分析关注的是量级,而不是具体的值;是趋势,而不是短暂的波动;关注的是变量,与常量无关。

大O表示法的运算规则:

  1. 加法运算法则。非嵌套代码结构下使用加法法则。如果 T1(n)=O(f(n)),T2(n)=O(g(n));那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))。
  2. 乘法法则。嵌套代码的代码结构下使用乘法法则。如果 T1(n)=O(f(n)),T2(n)=O(g(n));那么 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n)).

下面是几种常见的时间复杂度:

  1. 多项式时间复杂度。
    • O(1) 常量时间。最优。一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。
      • O(logn)、O(nlogn)。代码的执行路径树状,复杂度就是树的高度logn的情况。
      • O(m+n)、O(mn)。m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大,所以我们在表示复杂度的时候,就不能简单地利用加法法则,省略掉其中一个。所以,上面代码的时间复杂度就是 O(m+n)。针对这种情况,原来的加法法则就不正确了,我们需要将加法规则改为:T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效:T1(m)T2(n) = O(f(m) * f(n))。
  2. 非多项式时间复杂度。也叫作NP(Non-Deterministic Polynomial,非确定多项式)问题。当数据规模 n 越来越大时,非多项式量级算法的执行时间会急剧增加,求解问题的执行时间会无限增长。所以,非多项式时间复杂度的算法其实是非常低效的算法。典型的问题是旅行商问题。这类问题的都是找到最优解,相关的算法有模拟退火算法,遗传算法等。
    • O(2^n) 和 O(n!)。

这几种常见的复杂度的渐进大小关系如下:
O(n^2) > O(nlogn) > O(n) > O(logn) > O(1)

1.2 渐进空间复杂度分析

空间复杂度分析比时间复杂度分析要简单很多。算法的存储空间和数据规模增长的关系。常见的空间复杂度就是 O(1)、O(n)、O(n^2 ),像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。

1.3 最好、最坏和平均情况

在分析复杂度时,根据输入数据的不同特征,复杂性也是不同的。如在一个无序数组N中查找某一个数字,如果第一个就是则只用查找一次,如果没有则是n次。复杂度就是O(n),最好是O(1),最差是O(n),平均就是求期望的查找次数,需要考虑将要查找到额数出现在数组中的概率,然后计算期望。

1.4 均摊复杂度

有的时候,对于一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系。

这个时候,我们的分析思路就是:将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

2 事后统计测试分析法

事后统计测试法依赖于测试环境,软硬件;受测试数据集规模影响。在实践中,就是性能测试,配合profiling,找到程序的性能瓶颈。

性能测试还用于容量预估,知道什么样的体量下达到瓶颈,需要进行扩容,从而指导运维。

程序最终还是跑在具体的软硬件环境中的,所有必须要有性能测试。