积分应用

积分的应用
微积分是高等数学的基础，但我们搞程序的平时使到微积分的时候实在少之又少，反正我大四以前根本没有用到微积分（编写什么插值求积分那种程序不算），果真如此吗？？？
微积分的威力发挥在算法分析上，你会算法分析吗？会的话，肯定会体会到。看看积分的例子：
“有一个无序数列，每次遍历整个数列查找一个数，然后删除之，重复这个步骤直到数列为空，问这个算法的效率？”
这个你一眼就看出效率了，遍历的次数从1个增加到n个，那么平均是n/2个，一共执行n次，所以效率是n*n/2，也就是O(n*n)，呵呵，很简单，惬意的笑。但细想一想，为什么这里能把n除以2呢？是因为n是个线性函数，所以在计算时可以用它的中间值来计算。这种中间值概念的应用很普遍，很多算法效率的计算有需要，回忆在quick sort的效率分析里，因为整个数列里的每个数与第一个数（比较数）交换的概率相同，那就是绝对的线性关系（函数为常数），所以才可以用，2*T(k)代替T(k)+T(n-k)。
其实这题也可以用积分来算，效率实际上就是把n在1到n上取积分，也就是n*n/2，和先前的答案一样，注意这里，积分本身是一个连续的数学概念，这里扩展到离散求积分。
我们把上面的例子改改：
“有一个有序数列，每次用二分查找找到其中一个值，删除之，重复这个步骤直到数列为空，问这个算法的效率？“
想啊想啊，二分效率是log(n)，从log(n)降到log(1)，那么和先前的一样，效率是中间值*n，就是log(n)/2*n，也就是O(n*log(n))，我赶紧握着你的手说，“恭喜你，蒙对了！”，最终的答案确实是O(n*log(n))，但绝不是这么出来的，因为log函数不是线性函数，你绝对不能用中间值代替来进行计算。
哦！那该怎么计算呢？积分来了。上面的算法实际是对log操作从1增加到n，在数学上实际是离散的对log函数做1到n的积分，也就是对log(n)积分。那log(n)的积分怎么算呢？用Udi的《算法导引》的估计法，我们先估计其积分是n*n，我们对n*n求导
D(n*n)=2*n>log(n)
我们的估计大了，那么是不是n*log(n)呢？
D(n*log(n)) = D(n)*log(n) + n*D(log(n)) = log(n)+ n*1/n=log(n) +1
哇！我们对了，n*log(n)求导就是log(n)再和一个常数相加，于是可以判断log(n)的积分就是和n*log(n)一个等级的，于是，答案出来了，这个算法的效率是n*log(n)，这就是积分的威力。