java - 进行比较的最坏和最好的情况

Question

Given two arrays of double values, sorted in ascending order, one with 100 elements, the other with 10 elements, how many comparisons will it take in an optimal algorithm to merge these arrays into one sorted array, in the best case and in the worst case?

答案是:

Best Case: 10 Comparisons

Worst Case: 109 Comparisons

在您将我标记为家庭作业问题或愚蠢问题之前，请听我说完。我将解释我的推理并制作标题，就好像有人对迭代/比较有类似的问题，他们可以看看这个。

我理解 10 次比较的最佳情况，因为较短数组中的所有值都必须小于包含 100 个值的较大数组中的所有值。然后，您将只进行一次比较并对其进行排序。

但对于最坏的情况，我不会进行 109 次比较。我不知道这个问题是否要求使用合并排序来比较它，其中短数组中的每个单个数字将进行大约 7 次比较 (log2^100 = 6.64)，而 7 次 10 是 70 而不是 109。

我做错了什么吗？问题的答案也无济于事。如果你们都能理解和解释，我们将不胜感激。

即使有了答案，我也不明白比较是如何进行的以及使用了哪种类型的排序(如果使用的话)。有人能再看看吗？

Answer 1

对于最坏的情况，考虑一个场景

Array-1:1,2,3,4,5,6,7,8,9,110。
Array-2:10,11,12,13,14,15,......,109。

合并它们的最佳方法是比较两个数组的第一个元素(如果可用)，然后取最小的一个并在该数组中进一步处理。

所以这里如果我们计算总比较，Array-1 的前 9 元素将与 Array-2 的第一个元素进行比较，因为Array-2 的first 元素大于Array-1 的first 9 元素所以总比较= 9 到现在为止。

现在 array-1 的最后一个元素是所有元素中最大的，所以很明显它最终会在合并中出现 所有 元素仍然存在于 array-2 将与 array-1 的元素进行比较。

所以这总共需要 100 次比较。现在 总比较 = 100 + 9 = 109。所以在这种情况下，最坏的情况最多有 109 比较。

编辑:

合并代码:

Merge(int array1[],int array2[])
{
    int array3[]=new int[array1.length+array2.length];

    int point1=0;  //indicating current element of array1
    int point2=0;  //indicating current element of array2
    int point3=0;  //indicating current element of resultant array3

    while(point1<array1.length && point2<array2.length)
    {
        if(array1[point1]>array2[point2]) //This is to be counted as a comparison
        {
            array3[point3]=array2[point2]; //Take element of array2
            point2++;   //move to the next element of array2
            point3++;   //move to the next element of array3
        }
        else
        {
            array3[point3]=array1[point1]; //Take element of array3
            point1++;  //move to the next element of array1
            point3++;  //move to the next element of array2
        }
    }

    while(point1<array1.length)
    {
        array3[point3]=array1[point1]; //Take element of array3
        point1++;  //move to the next element of array1
        point3++;  //move to the next element of array2
    }

    while(point2<array2.legnth) 
    {
        array3[point3]=array2[point2]; //Take element of array2
        point2++;   //move to the next element of array2
        point3++;   //move to the next element of array3    
    }
}

所以这里当我们比较两个数组的元素时，就算作一次比较。对于最好的情况，

Array-1 = 1,2,3,4,5,6,7,8,9,10。
Array-2 = 11,12,13,14,.....,110。

所以这里的总比较将为 10，在 10 比较之后，Array-1 将变为空(所有元素都被取出)。所以不会再做更多的比较。因此，最好情况下的总比较数是 10。

如果您想打印任何输入的总比较，请对算法进行少量更改。

定义一个变量 int total_comparisons=0; 然后每次进行比较时，将其递增。所以改变比较条件:

if(total_comparisons++ && array1[point1]>array2[point2])//这个要算作比较

最后打印total_comparisons。这是您理解逻辑的更好方式。