最优合并问题的时间复杂度怎么算

Question

如题所述

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(符号打不出来,就用这个代替吧,^_^), 具体可以参考一下机械工业出版社的《算法导论》
参考资料： 机械工业出版社《算法导论》