
Mellin 变换可以用来做渐近分析。
对于复数 ,函数 的 Mellin 变换定义为
Mellin 变换有两个下面会用到的性质(为方便起见下标里带了 )
从定义可以看到,如果 ,则 在带 上有定义(叫 fundamental strip),事实上 在这个区域上解析,并且 和 是 的极点。
这就启发了我们可以通过研究 的极点去研究 在 和 处的阶。我们这里只关注收敛的情形,即 。当 为 的非本性极点时,假设 Laurent 展开的主要部分是 ,那么可以证明,如果 可以向右开拓(meromorphic continuation,下同)至 ,则
利用性质(1),从上式可以直接得到 时的结论:如果 可以向左开拓至 ,则
也就是说,利用 Mellin 变换,如果上面的展开式中只有有限项,那我们可以一次性地把 在 趋向 或 时形如 的收敛阶找出来( 项来源于性质(2))。
Average Case Analysis of Algorithms on Sequences 第9章列举了 Mellin 变换在算法分析上的一些应用,没有细看所以就不抄了。
