首页 文章

合并排序的最坏情况何时会发生?

提问于
浏览
28

我知道mergesort的最坏情况是O(nlogn),与普通情况相同 .

但是,如果数据是升序或降序,则会导致最小比较次数,因此mergesort变得比随机数据快 . 所以我的问题是:什么样的输入数据产生最大数量的比较,导致mergesort变慢?

this问题的答案是:

对于某些排序算法(例如快速排序),元素的初始顺序可能会影响要完成的操作数 . 然而,它不会对mergesort进行任何更改,因为它必须完全执行相同数量的操作:递归地划分为小数组,然后将它们合并回来,总Θ(nlogn)时间 .

但这是错误的 . 在这一点上,我们有两个子阵列,如果初始数据已经排序,我们想要合并它们,我们将只进行n / 2次比较 . 这是第一个子阵列的所有元素,只有第二个数组的第一个元素 . 但是,我们可以实现更多目标 . 我正在寻找输入数据 .

2 回答

  • 63

    合并排序的最坏情况将是合并排序必须做的事情 maximum number of comparisons.

    所以我将尝试以自下而上的方式构建最坏的情况:

    • 假设排序后的最后一步数组是 {0,1,2,3,4,5,6,7}

    • 对于最坏的情况,此步骤之前的数组必须为 {0,2,4,6,1,3,5,7} ,因为此处左侧子阵列= {0,2,4,6} 且右侧子阵列= {1,3,5,7} 将导致最大比较 . (在左右子阵列中存储备用元素)

    Reason: 数组的每个元素至少会进行一次比较 .

    • 为前面的步骤对左和右子阵列应用相同的上述逻辑:对于数组 {0,2,4,6} ,最坏的情况是如果前一个数组是 {0,4}{2,6} ,对于数组 {1,3,5,7} ,最坏的情况将是 {1,5}{3,7} .

    • 现在对前面的步骤数组应用相同的内容:对于最坏的情况: {0,4} 必须是 {4,0}{2,6} 必须是 {6,2}{1,5} 必须是 {5,1} {3,7} 必须是 {7,3} . 好吧,如果你看清楚这一步是 not necessary 因为如果set / array的大小是2那么每个元素将至少比较一次,即使大小为2的数组被排序 .

    现在自上而下分析情况

    Applying Merge Sort using Divide and Conquer
    
    Input array arr[] = [4,0,6,2,5,1,7,3]
                               /  \
                              /    \
                      [4,0,6,2] and [5,1,7,3]
                         / \           / \
                        /   \         /   \
                     [4,0] [6,2]    [5,1] [7,3]       Every pair of 2 will be compared atleast once therefore maximum comparison here
                       |     |        |     |
                       |     |        |     |
                     [0,4] [2,6]    [1,5] [3,7]      Maximum Comparison:Every pair of set is used in comparison     
                       \     /        \     /                        
                        \   /          \   /
                     [0,2,4,6]      [1,3,5,7]        Maximum comparison again: Every pair of set compared
                          \             /
                           \           / 
                         [0,1,2,3,4,5,6,7]
    

    Now you can apply the same logic for any array of size n

    下面是实现上述逻辑的程序 .

    注意:以下程序仅对2的幂有效 . 这是为任何大小为n的数组提供最坏情况的通用方法 . 您可以自己尝试使用不同的数组进行输入 .

    class MergeWorstCase
    {
        public static void print(int arr[])
        {
            System.out.println();
            for(int i=0;i<arr.length;i++)
                System.out.print(arr[i]+" ");
            System.out.println();
        }
        public static void merge(int[] arr, int[] left, int[] right) {
            int i,j;
            for(i=0;i<left.length;i++)
                    arr[i]=left[i];
            for(j=0;j<right.length;j++,i++)
                    arr[i]=right[j];
        }
    
        //Pass a sorted array here
        public static void seperate(int[] arr) { 
    
                if(arr.length<=1)
                    return;
    
                if(arr.length==2)
                {
                    int swap=arr[0];
                    arr[0]=arr[1];
                    arr[1]=swap;
                    return;
                }
    
            int i,j;
            int m = (arr.length + 1) / 2;
            int left[] = new int[m];
            int right[] = new int[arr.length-m];
    
            for(i=0,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in left subarray
                left[j]=arr[i];
    
            for(i=1,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in right subarray
                right[j]=arr[i];
    
            seperate(left);
            seperate(right);
            merge(arr, left, right);
        }
        public static void main(String args[])
        {
            int arr1[]={0,1,2,3,4,5,6,7};
            seperate(arr1);
            System.out.print("For array 1:");
            print(arr1);
            int arr2[]={0,1,2,3,4,5,6,7,8};
            seperate(arr2);
            System.out.print("For array 2:");
            print(arr2);            
        }
    }
    

    输出:

    For array 1:
    4 0 6 2 5 1 7 3 
    For array 2:
    8 0 4 6 2 5 1 7 3
    
  • 4

    算法

    我的一位教授给我的一个简洁的算法使用相反的方法解决了这个问题 . 您可以从基本案例开始并遵循递归模式,而不是将初始数组拆分为越来越小的块 .

    基本情况是[1]和[2,1],它们是大小为 12 的最坏情况数组的示例 . 从中为您构建 34 的数组,如下所示 .

    • 取两个大小为 nm 的数组,例如 n + m = x ,其中x是您要查找的大小

    • 将它们组合在一起,将较小尺寸的数组放在顶部

    • 加倍顶部数组中的每个元素

    • 将每个元素加倍并从底部数组中减去1

    使用此算法,这是大小为 34 的数组的一系列步骤 .

    例子

    尺寸3

    • [1] + [2, 1]

    • 你得 [1 | 2, 1]

    • [2 | 2, 1]

    • [2 | 3, 1] -> [2, 3, 1]

    尺寸4

    • [2, 1] + [2, 1]

    • 你得 [2, 1 | 2, 1]

    • [4, 2 | 2, 1]

    • [4, 2 | 3, 1] -> [4, 2, 3, 1]

    尺寸7

    • [2, 3, 1] + [4, 2, 3, 1]

    • 你得 [2, 3, 1 | 4, 2, 3, 1]

    • [4, 6, 2 | 4, 2, 3, 1]

    • [4, 6, 2 | 7, 3, 5, 1] -> [4, 6, 2, 7, 3, 5, 1]

    很容易看出如何采用这种方法并轻松构建大型数组 .

    计划

    这是一个实现此算法的python函数 .

    import math
    
    def worstCaseArrayOfSize(n):
        if n == 1:
            return [1]
        else:
            top = worstCaseArrayOfSize(int(math.floor(float(n) / 2)))
            bottom = worstCaseArrayOfSize(int(math.ceil(float(n) / 2)))
            return map(lambda x: x * 2, top) + map(lambda x: x * 2 - 1, bottom)
    

相关问题