|
算法好坏的标准主要是从时间和空间两个方面来考虑的。为了有一个统一的比较标准，就出现了许多算法效率的估算和分析的方法。
记得大二学习数据结构的时候，一直对“分析技术”望而生畏。最近又拿起了久违的《数据结构与算法分析》这本书啃起来。总算对“均摊分析”有了一点小小的心得。在这里记下来。
“均摊分析是对一组操作的分析。特别是均摊分析允许处理这样一种情况， n个操作在最差情况下的代价小于任何一个操作在最差情况下的代价的n倍。均摊分析并不是把注意力集中到每个操作的单独代价，然后再把他们加起来，而是看到整个一组操作的代价，再把整体的代价分摊到每一个单独的操作上去。”
这个是书上的原话，主要提供了两个信息：
- 均摊分析处理的情况不是单个操作的简单叠加。也就是说在这种情况下如果一次操作的代价是m,那么进行n次操作的代价并不是 (n * m)。其实这种情况是很常见的。因为代价的分布并不平均。在后面的例子中可以看到。
- 均摊分析的思路是从整体上对算法的效率进行把握。而不是从一次操作的情况来对算法效率定论。因为是一组操作。那么就不同与一次操作。这里就涉及到一个概率的分布的因素，最有名的就是2/8原则，这些概率的分布对算法的效率造成了很大的影响。
下面是两个书上的例子及分析：
【例1】分析对一组未排序的数组进行一组顺序检索的情况。
如果简单的分析，一次顺序查找的最差情况是找到最后一个元素才找到。那么对于一个长度为n的序列，检索的最差代价是n。如果这样的循序查找执行了n次，那么检索代价就是 (n * n)。但是，如果我们现在的情况是检索的n次中每次都是检索不同的值，也就是n次检索以后，基本数组中的每一个值都被检索了一遍。这种情况下某些元素的检索代价会很高，比如数组最后一个元素。而有些元素的检索代价却很低，比如数组的第一个元素。那么这个时候最差的检索代价是（1+2+3+...+n)，即 n2/2。
【例2】考虑一下一个二进制计数器加1的过程。
算法要把低位（最右边）向高位（最左边）移动，把1变成0，直到碰到第一个0，把这个0变成1，这样加一操作就完成了。假定一个长度为n的二进制数存储在一个长度为n的数组中。简单的最差情况分析认为，如果所有n位都是1（除最高位），那么n位都需要处理。这样如果有2n次加1操作，那么代价就是 n2n。这个代价就太高了，因为很少有这么多位需要处理。实际上，有一半的时间最低位是0，因此只有这个位需要处理。有四分之一的时间低两位是01，因此只有低两位需要处理。看待这个问题的另一种方式是低位总要翻转，其左边的位有一半的时间需要翻转，下一位有四分之一的时间需要翻转，依此类推。可以通过求和得到它（从右到左计算位的代价）：1＋1/2 ＋1/4 ＋．．． ＜2，也就是说，每次加1操作翻转位的平均数是2，对于一组2n次的加1操作，总代价只有2*2n。
从上面两个例题再来看看均摊分析的定义。可以知道均摊分析是建立在一组操作的情况下的。由于是一组操作，那么不同的情况就会有不同的概率问题。这个时候就不能用简单的单操作叠加的方式来对算法的状态进行分析了。而应该根据具体的数据分布来对算法效率进行评估，最后进行选择。
觉得自己理解的还不是很深刻，欢迎大家和我交流。 | 
转播
