1

这是我试图分析的算法（见下文）。我不明白为什么 O(n)当合并排序具有时间复杂度时O(n logn)，它们似乎都在做同样的事情。

那么两者都具有相同的 j 时间复杂度，如果您将 j 保留为行，则2^j X c(n/2^j)=cn并且它们的运行时间均为log n，其中 n 是元素的数量。

Algorithm: BinarySum(A, i, n)
Input: An array A and integers i and n.
Output: The sum of the n integers in A starting at index i.
if n = 1 then
return A[i]
return BinarySum(A, i, [n/2] ) + BinarySum(A, i + [n/2], [n/2])

谢谢，丹尼尔

4

3 回答 3

2

您正在处理数组的每个成员的恒定时间。不管你怎么做，最终的复杂度都是 O(n)。顺便说一下，如果你用纸笔法做一个简单的例子，你会发现实际上你是按照它们在数组中出现的顺序来调用数组的元素，这意味着这个算法相当于简单的迭代求和。

O(n) 复杂度的正式证明直接来自主定理。您的算法的递归关系是

T(n) = 2 T(n/2)

定理的情况 1 涵盖了这一点。从这个复杂度计算为

O(n ^ log_2_(2)) = O(n)

至于归并排序，其递推关系为

T(n) = 2 T(n/2) + O(n)

这是一个完全不同的故事——主定理的案例 2。

于 2012-08-09T13:40:35.243 回答
0

您的算法的递归公式是；

 2T(n/2) = O(n)

而归并排序的递推公式是；

 2T(n/2) + O(n) = O(n log n)

因为有两个递归调用+一个对需要 O(n) 的合并函数的调用。您的函数只进行了两次递归调用，请查看细分；

http://www.cs.virginia.edu/~luebke/cs332.fall00/lecture3/sld004.htm

于 2012-08-09T13:29:01.447 回答
0

考虑以下伪代码：

 1    MergeSort(a, p, r)
 2      if  P<r                                // check for base case
 3      then q = FLOOR p+r/2                   // Divide
 4      MergeSort(a, p, q)                     // conquer
 5      MergeSort(a, q+1, r)                   // conquer
 6      Merge(a, p, q, r)                      // Merge

现在复杂度如下：

为了

第 3 行：- O(1) 因为它需要恒定的时间。

第 4 行：- T(n/2) 因为它对一半元素进行操作。

第 5 行：- T(n/2) 因为它对一半元素进行操作。

第 6 行：- T(n) 因为它对所有元素进行操作

现在使用@Lunar 提到的递归关系，我们可以声明时间复杂度等于：- O(nlgn)

于 2016-06-25T14:14:18.593 回答