每周学点大数据 | No.7大数据规模的算法分析

No.7期

大数据规模的算法分析

Mr. 王：这样的时间界限记为O(1)，我们称之为常数时间算法，这样的算法一般来说是最快的，因为它与输入规模完全无关，不论输入规模n多么大，我们都可以用一个与输入规模n无关的常数时间得出结论，相比于巨大的n来说，这个常数在数量级上已经微乎其微了。

另外，与大O记号类似，常用的记号还有Θ，Θ(g(n)) 表示函数f(n)构成的集合，存在n0，c1，c2。当n≥n0时，0≤c1g(n)≤f(n)≤c2g(n)。这样保证了当n足够大时，f(n) 在一个常数因子范围内与g(n)是相等的，g(n)是f(n)的一个渐进确界。比如T(n)=2n+3，同样也符合Θ(n)。此时我们称f(n)和g(n)是同阶的函数。

相应的， 还有Ω记号，Ω记号表示函数f(n)构成的集合，存在n0，c1，c2，当n≥n0时，0≤cg(n)≤f(n)。换句话说，g(n)是f(n)的低阶函数，或者说g(n)是f(n)的下界。

如果希望大小关系不包含等于，则还有ω和o两种记号。其中ω(g(n))表示存在n0，c1，c2，当n≥n0时，0≤cg(n)≤f(n)；而o(g(n))表示存在n0，c1，c2，当n≥n0时，0≤f(n)<cg(n)。它们与大O记号和Ω记号类似，只是在大小关系上不包含等于。

小可：嗯，听到这里，我理解了如何进行算法的分析和几种记号表示的含义了。

Mr. 王：另外，很多时候，算法的运行时间并不是稳定的，在算法分析的过程中，我们还要考虑算法运行的最好情况、最坏情况和平均情况。很多算法的最好情况非常好，但平均情况不够理想；而有的算法运行时间的最坏情况复杂度非常高，但平均情况却不错。

这里我们举个例子来说吧。对于一个存放了100个整数元素的数组，而且这些整数是无序的，我们要从中找到一个数字50。这就存在最好情况和最坏情况。

小可：我明白了，如果使用逐个访问数组中每个元素的算法，最好情况是一比较发现第一个元素也就是A[0]恰好是50，那就不用再往后比较了，只进行一次比较就找到了50 ；最坏情况就是逐个比较下去，发现最后一个元素是50，或者最后一个元素也不是50，则说明数组中不存在50这个元素。这时候要对每个元素都进行一次比较，这里有100个元素，就进行了100次比较。

Mr. 王：那算法的最好和最坏情况复杂度如何呢？

小可：如果有n个元素，在最好情况下，可以以常数时间找到我们所要找的元素，也就是O(1)；在最坏情况下，我们要和最后一个元素进行比较才能得出结论，就是要进行和数据规模n相关的次数比较，也就是O(n)。

Mr. 王：嗯，对于很多算法来说，用最好和最坏情况都不能够最佳地代表一个算法的复杂度。就拿这个例子来说，用最好情况来代表算法的复杂度显然是不恰当的，因为我们要找的元素往往不能总是第一个元素，如果这些元素是随机分布的，只有1/n的概率让其出现在第一个位置上。同理，我们要找的元素恰好出现在最后一个位置上的概率也是1/n，所以说它的运行时间就是访问n个元素的运行时间显然也不够公平。因此，很有必要给出一种复杂度，叫作平均复杂度，顾名思义，平均复杂度就是算法运行的平均情况的时间复杂度，既不是最好的，也不是最坏的，而是所有情况的平均值，或者说是在所有情况下复杂度的数学期望，很多时候，平均复杂度能最好地概括一个算法的运行情况。那么，从数组中逐个搜索一个元素的算法的平均情况如何呢？

小可：如果元素是随机分布的，元素出现在数组中每一个位置上的概率就是均等的，所以期望的运行时间应该是访问n/2个元素的时间，也就是O(n/2)。不过，这个值好像也是O(n) 啊。

Mr. 王：嗯，对于这个算法来说，平均情况和最坏情况的复杂度是同数量级的；但对于一些算法来说，最坏情况的复杂度却要比平均情况高一个数量级，用最坏情况去衡量它的复杂度就会将其评价为不够快的算法，这也不够公平。所以对于很多算法来说，我们要考虑它的最好、最坏和平均情况，以便更好地估计一个算法运行的真正时间。

内容来源：灯塔大数据