合并排序空间和时间复杂度 [英] Merge sort space and time complexity

问题描述

给出以下合并排序算法：

Given the following merge sort algorithm :

mergesort(A,p,r) 

    if (r <= l) return    //constant amount of time
    int m = (p+r)/2       //constant amount of time

    mergesort(A, p, q)      // these two calls will decide the
    mergesort(A, q+1, r)    // O(logn) factor inside O(n * logn) right?

    merge(A, p, q, r)       lets dwell further


merge(a,p,q,r){

    n1 = q-p+1         //constant time
    n2 = r-q           //constant time

    // Let L[1...n1+1] and R[1...n2+1] be new arrays    // idk , lets say constant

    for i,j in L[],R[]
        L[i] = A[p+i-1]
        R[j] = A[q+j]  // shouldn't this take time varying on size of array?
                       // also extra space too?

    i=1 j =1           // constant time

    for k = p to r     // everything below this will contribute to O(n)
                       // inside O(n*logn) amirite?
        if L[i]<=R[j]
            A[k] = L[i]
            i++

        else A[k] = R[j]
             j++

为什么我们要估算 O（nlogn ）的时间复杂度，请记住要创建要合并的左右数组吗？

How come we are estimating O(nlogn) time complexity for it , keeping in mind that there are left and right arrays being created to be merged back?

空间复杂度又如何仅在使用额外大小的情况下， O（n）是什么？他们两个不会增加 n ，因为填满数组需要 O（n）和<$在每个递归步骤中都将创建c $ c> L [] 和 R [] 。

And how come space complexity is O(n) only if extra size is being used? Won't the two of them be increased by n, because filling up array takes O(n) and L[] and R[] are being created at each recursion step.

推荐答案

我建议您在纸上画一棵树来说明这一点：首先写下整个数组：

I suggest you reason about this by drawing a tree on paper: first write down your whole array:

2 4 7 1 4 6 2 3 7 ...

然后写出递归导致其拆分的内容：

Then write what the recursion causes it to be split in below it:

 2 4 7 1 3 4 6 2 3 7 ...

          |
2 4 7 1 3   4 6 2 3 7 ...

    |            |
2 4   7 1 3  4 6   2 3 7

以此类推。

然后，计算您已写了多少行。这将接近您开始使用的元素数量的以2为底的对数（ O（log n））

Then, count how many rows you've written. This will be close to the base 2 logarithm of the number of elements you started with (O(log n)).

现在，每行要完成多少工作？ O（n）。合并两个长度为 n1，n2 的数组将花费 O（n1 + n2），即使您必须分配空间为他们服务（并且您没有正确实施）。由于递归树中的每一行都有 n 个数组元素，因此，每一行完成的工作是 O（n），因此整个算法为 O（n log n）。

Now, how much work is being done for each row? It's O(n). Merging two arrays of lengths n1, n2 will take O(n1 + n2), even if you have to allocate space for them (and you don't in a proper implementation). Since each row in the recursion tree has n array elements, it follows that the work done for each row is O(n) and therefore the entire algorithm is O(n log n).

而且，只有使用额外的大小时，空间复杂度才是O（n）吗？不会将它们两个都增加n，因为填充数组需要O（n），并且在每个递归步骤中都会创建L []和R []。

And how come space complexity is O(n) only if extra size is being used? Won't the two of them be increased by n , because filling up array takes O(n) and L[] and R[] are being created at each recursion step.

这更有趣。如果确实在每个递归步骤中都创建了新的 L，R 数组，那么空间复杂度将为 O（n log n）。但是你不这样做。在开头创建一个额外的数组，大小为 n （将其视为全局变量），然后将每个合并的结果存储到其中。

This is more interesting. If you do indeed create new L, R arrays at each recursion step, then the space complexity will be O(n log n). But you don't do that. You create one extra array of size n at the beginning (think of it as a global variable), and then you store the result of each merge into it.

您只能传递可帮助您识别子数组的内容，例如它们的大小和它们开始的索引。然后，您可以使用原始数组访问它们，并将合并结果存储在全局分配的数组中，从而导致 O（n）额外的空间：

You only pass around things that help you identify the subarrays, such as their sizes and the indexes they begin at. Then you access them using the original array and store the result of the merge in the globally allocated array, resulting in O(n) extra space:

global_temp = array of size equal to the array you're sorting
merge(a,p,q,r){

    i=p 
    j =q              // constant time

    while i < q and j <= r // or a similar condition       
        if A[i]<=A[j]
            global_temp[k++] = A[i]
            i++

        else 
            global_temp[k++] = A[j]
            j++
     // TODO: copy remaining elements into global_temp
     // TODO: copy global_temp into A[p..r]

这篇关于合并排序空间和时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！