问O符号和合并两个已经排序的数组
EN

Stack Overflow用户

提问于 2021-05-23 09:11:32

回答 2查看 391关注 0票数 1

我被告知将两个已经排序的数组，大小不同的A和B合并成一个数组，C在线性时间内。

通过线性时间，我知道这个算法的时间复杂度必须是O(n)。后来，我还被告知在合并数组时执行排序。

我的一个想法是创建一个算法，在两个数组中都有两个指针，指向最小的元素。指向的最小元素将进入新的数组。当一个数组耗尽时，另一个数组的其余元素将复制到新数组中。

由于我几个月前刚开始编程，我发现这很难实现，因此我决定执行合并排序(MS)，因为它最类似于上面提到的算法。然而，我关心的是MS本身的时间复杂性- O(nlogn)

然而，考虑到这两个数组已经被排序，MS的时间复杂度会降低还是保持不变？

提前谢谢。

algorithm

sorting

time-complexity

mergesort

回答 2

Stack Overflow用户

回答已采纳

发布于 2021-05-23 09:48:58

您的任务是实现合并算法的合并阶段。mergesort具有O(N.log(N))对数据集排序的复杂性，但每个合并阶段的线性时间与合并集的长度成正比。

以下是这方面的伪代码：

merge(array a, array b into array c)
    int i = 0, j = 0, k = 0;
    while (i < len(a) and j < len(b)) {
        if (a[i] <= b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
        }
    }
    while (i < len(a)) {
        c[k++] = a[i++];
    }
    while (j < len(b)) {
        c[k++] = b[j++];
    }
}

复杂度是线性的，因为每个循环中的每个步骤都将一个元素复制到c数组中，总共需要len(a) + len(b)步骤。

票数 4

Stack Overflow用户

发布于 2021-05-23 09:56:01

将两个大小不同的数组合并成一个数组，C为线性时间。

int *mergeArrays(const int *array1, const int *array2, size_t size1, size_t size2, int asc)
{
    int *result = malloc((size1 + size2) * sizeof(*array1));
    size_t index1 = 0, index2 = 0;
    size_t i;


    for(i = 0; i < size1 + size2 && index1 < size1 && index2 < size2; i++)
    {   
        if(asc)
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
        else
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
    }
    if(index1 == size1) memcpy(result + i, array2 + index2, sizeof(result) * (size2 - index2));
    if(index2 == size2) memcpy(result + i, array1 + index1, sizeof(result) * (size1 - index1));
    return result;
}

https://godbolt.org/z/PY8Ysv319

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void sort(int *array, size_t size)
{
    qsort(array, size, sizeof(array[1]), cmpfunc);
}

int *mergeArrays(const int *array1, const int *array2, size_t size1, size_t size2, int asc)
{
    int *result = malloc((size1 + size2) * sizeof(*array1));
    size_t index1 = 0, index2 = 0;
    size_t i;


    for(i = 0; i < size1 + size2 && index1 < size1 && index2 < size2; i++)
    {   
        if(asc)
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
        else
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
    }
    if(index1 == size1) memcpy(result + i, array2 + index2, sizeof(result) * (size2 - index2));
    if(index2 == size2) memcpy(result + i, array1 + index1, sizeof(result) * (size1 - index1));
    return result;
}

int main(void)
{
    srand(time(NULL));
    size_t size1 = rand() % 20, size2 = rand() % 20;
    int *mergedArray;

    if(size1 < 5) size1 += 5;
    if(size2 < 5) size2 += 5;

    int array1[size1], array2[size2];

    for(size_t i = 0; i < size1; i++)
        array1[i] = rand();
    for(size_t i = 0; i < size2; i++) 
        array2[i] = rand();
    sort(array1, size1);
    sort(array2, size2);

    for(size_t i = 0; i < size1; i++)
        printf("array1[%2zu] = %d\n", i, array1[i]);
    for(size_t i = 0; i < size2; i++)
        printf("array2[%2zu] = %d\n", i, array2[i]);

    mergedArray = mergeArrays(array1, array2, size1, size2, 1);
    for(size_t i = 0; i < size2 + size1; i++)
        printf("result[%2zu] = %d\n", i, mergedArray[i]);
}