二路归并的算法复杂度(2)

终于明白了,是这么回事。
二路归并时,假设两个Sequences为A和B,长度分别是n1和n2
那么,对A的每个元素需要在B中执行一次Find操作。
而Find操作的算法复杂度是O(n)
那么整体的,关于comparison的 算法复杂度就是O(n*n)
《Algorithm Design》这本书上是这么推的

但是如果从另一个角度来看。
每进行一次comparison就有一个元素被追加到结果集中。
那么,最多有n1+n2个元素,最多执行2*min(n1,n2)次comparison.
它的关于comparison的算法复杂度其实是O(n)

算法复杂度为O(n)的算法,典型的一类就是:需要对input中的每个元素,依次执行某个操作,且对于每个元素该操作所花费的运算时间是常量(O(1)),例如,find, sum, etc. 但是其实此处就给了我们一个很好的例子,该操作的运算时间不是常量(大于O(1)),但是整体的算法复杂度依然是O(n)。

这就让人产生的疑惑是,递归函数的算法复杂度该怎么去计算?很多时候,它不是一目了然的。

此博客中的热门博文

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

在windows下使用llvm+clang

tensorflow distributed runtime初窥