考虑如下递归式：
两边同时乘以 
得到：
要想转化成可以求和的递归式，那么必须有：
也就是：
这时令
得到：
这时就可以转化为求和了，解出：
所以
例题1
设 n 个数快速排序的操作次数为 
，那么有
用 
取代 n 可以得到
两式相减可以得到
由上面方法可以得到
所以
进而可以求出
这里介绍一个概念叫做调和级数：
所以
考虑如下递归式：
两边同时乘以 得到：
要想转化成可以求和的递归式，那么必须有：
也就是：
这时令
得到：
这时就可以转化为求和了，解出：
所以
设 n 个数快速排序的操作次数为 ，那么有
用 取代 n 可以得到
两式相减可以得到
由上面方法可以得到
所以
进而可以求出
这里介绍一个概念叫做调和级数：
所以
