一个时间复杂度的问题

Question

一个递归函数，要求它的时间复杂度。有难度，请高手帮忙！！
void mergesort（inti，intj）
{
int m；
if（i！=j）
{
m=（i+j）/2;
mergesort(i,m);
mergesort(m+1,j);
merge(i,j,m);
}
现在调用以上函数，调用方式：mergesort（0，n-1),其中的merge函数非递归函数，其时间复杂度为O(n）。

若能顺便归纳介绍一下递归函数的时间复杂度就更好了，谢谢！
http://zhidao.baidu.com/question/67433428.html?quesup1

Answer 1

一般来说, 标准的分治法合并排序时间复杂度为O(n * lg n), 略小于插入排序的O(n*n), 递归式的时间复杂度求解方法比较多,有画图分析法, 算式求解即类似于 T(n) = f(T(n-1))的求解方法, 还有就是凭经验猜然后用数学归纳法证明等等, 对于你的问题最直观的方法就是画图法, 这是一个二叉树问题, 最开始的序列被递归地分为两份, 因此这棵树的高度为lg n的下取整(这里我们不讨论取整的细节), 层数为1 + lg n, 每一层的合并排序代价总和都为c*n(c为某个常数), 因此整棵树代价为c*n*lg n + c*n, 因此时间复杂度为O(n*lg n);
也可以用他的表达式求解,这个问题的表达式为:T(n)=2*T(n/2)+O(n)
严格来讲,上面所说的O更好的替代品为theta(符号打不出来,就用这个代替吧,^_^), 具体可以参考一下机械工业出版社的《算法导论》

参考资料：机械工业出版社《算法导论》

Answer 2

O(nlgn)

对于时间复杂度，最容易理解的就是把它看做一颗树，每个根节点有两个儿子，做儿子代表(being, mid), 有儿子代表(mid, start)
最后形成一颗2叉树
深度为lgn，即为其复杂度，再乘以线性的O(n)
总复杂度nlgn

没有图，不太好说。你的书上后面章节肯定有2叉树，就是那个形式，可以先看一下，只看形式就可以，就很好理解了。