二路归并的算法复杂度

问题:A,B是两个Sorted Sequences.现在要把它们归并为一个Sorted Sequence.
例如,A是1,3,5,7,B是2,4,6,8,结果是1,2,3,4,5,6,7,8

二路归并算法的细节我就不细述了,学过一点算法的人都会。
现在问,这个算法的复杂度究竟是多少?

很多书上都说是O(n),但是我觉得不尽然。
它需要做O(n的平方)次comparison, O(n)次Select和Add.
如果Sequences内的元素是int这样的基本数据类型,那么comparison无所谓,所花的时
间非常少。
但是如果它的元素是长度为1024的整数数组。那么复杂度就大变了。
再者,简单点说,它的元素是字符串。怎么办?
这个算法复杂度就很难衡量的。

我觉得,如果泛泛而谈,它的算法复杂度应该是O(n的平方)。
因为在算法复杂度理论中有这样一条定理,如果对每个元素的运算需要分两步,第一步
的复杂度是O(a),第二步的复杂度是O(b),那么整体的复杂度应该是O(max(a,b))。
这个定理通过数学中同阶无穷大的性质是很容易证明的。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥