分治法与贪心法

 （1）逆序对问题

设A[1,….n]是一个包含n个不同非负整数的数组。若果i<j的情况下，有A[i]>A[j]，则（A[i],A[j]）就称为A中的一个逆序对。请设计一个时间复杂度不超过O(n*lgn)的算法并编程实现，统计任意长度的数组A中全部逆序对的个数。

（2）最优合并问题

给定k个有序序列s1 , s2,... , sk , 用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少（要求输出相应的合并顺序）。

---

上机12    逆序对问题

 

—、分治法

2、算法思想

     可以使用分治法解决上面问题。具体如下：利用归并方法给序列排序，将n个元素划分为n 个子序列，相邻的两个子序列进行规并操作：

1. 如果前一个子序列a1第一个元素大于后一个子序列a2第一个元素时，把a1的第一个元素放到归并序列中，同时把a1序列的第一个元素下标加1和归并子序列的最后一个元素下标加一。
2. 如果前一个子序列a1第一个元素小于后一个子序列a2第一个元素时，把a2的第一个元素放到归并序列中，同时把a2序列的第一个元素下标加1和归并子序列的最后一个元素下标加1，还有的是通过a1的最后一个元素的下标减第一个元素的下标得出a1目前子序列的长度，用计数器（初始为0）记录该a1长度，并把每次的记录累加。

依次进行每一对子序列归并操作。操作完成后，把该归并后的新的子序列再进行归并操作，直到规模子序列数量只剩下1个。

 

1. 实现代码及运行结果  

程序源代码如下

#include <stdio.h>

 

#define LEN 100 //宏定义数组的大小

 

int tmp[LEN] = {};

 

int n;

 

int counter = 0;

 

void _mergeSort(int * array, int start, int middle, int end)

{

int i, j, k;

int second = middle + 1; //第二个子序列开始的下标

int first = start; //第一个子序列开始的下标

int index = start; //tmp数组开始的下标

while(first <= middle && second <= end)

{

if(array[first] <= array[second])

{

tmp[index] = array[first];

first++;

index++;

}

else

{

tmp[index] = array[second];

counter = counter + middle - first + 1;

second++;

index++;

}

}

if(first > middle)

{

for(i = second; i <= end; i++)

{

tmp[index] = array[i];

index++;

}

}

else

{

for(i = first; i <= middle; i++)

{

tmp[index] = array[i];

index++;

}

}

for(first = start; first <=end; first++)

{

array[first] = tmp[first];

}

}

 

void MergeSort(int * array, int start, int end)

{

int mid, i, j, k;

if(start >= end)

return;

mid = (start + end) / 2;  

MergeSort(array, start, mid); //递归划分左边的数组

MergeSort(array, mid+1, end); //递归划分右边的数组

_mergeSort(array, start, mid, end); //对有序的两个数组进行合并成 //一个有序的数组

}

 

int main()

{

int i,array[LEN];

printf("请输入你要输入的数字个数：");

scanf("%d",&n);

for(i = 0; i < n; i++)

{

scanf("%d",&array[i]);

}

MergeSort(array, 0, n-1);

printf("逆序对有%d个\n",counter);

return 0;

}

 

实验结果

 

当输入6个数（6,5,4,3,2,1），程序运行结果见下图，达到预期结果。

当输入7个数（5,3,2,6,4,3,1），程序运行结果见下图，达到预期结果。

• 复杂度分析及算法改进

 

1. 时间复杂度

    _mergeSort()函数的时间复杂度为O(n)，因为代码中有2个长度为n的循环（非嵌套），所以时间复杂度则为O(n)；

      简单的分析下元素长度为n的归并排序所消耗的时间 T[n]：调用MergeSort()函数划分两部分，那每一小部分排序好所花时间则为  T[n/2]，而最后把这两部分有序的数组合并成一个有序的数组_mergeSort()函数所花的时间为  O(n)；

公式：T[n]  =  2T[n/2] + O(n)

所以得出的结果为：T[n] = O( nlogn )

1. 空间复杂度

以上程序主要占用空间一个是归并放置数组，空间复杂度为o（n）；另一个是被归并数组空间复杂度为o(n)；所以总的空间复杂度为o(n)；

（3）算法改进
可以采用三路归并，达到减少递归层次的作用

---

上机12(2)   最优合并问题

• 贪心算法

1. 算法思想

可以使用贪心算法解决上述问题。具体如下：把n个序列合并为一个序列，需要进行n次合并。用堆排序分别把各序列的两个最短子序列拿出来，用归并法把它们合并，这次合并也是比较次数最少的合并，这样可以做到每次合并到是最优合并，然后用一个计数器把每次比较次数都叠加起来，得到把n个子序列合并为一个序列的总次数。

 

1. 实现代码及运行结果

程序源代码如下：

#include <stdio.h>

#include <string.h>

 

//调整小根堆

void HeapAdjust(int * a, int s, int len)

{

int i, j, k, t;

t = a[s];

for(i = 2 * s + 1; i <= len; i = i * 2 + 1)

{

if(i < len && a[i] > a[i+1]) //求两个子节点关键码较小的节点

{

i++;

}

if(t < a[i]) //如果该根结点比子节点小时,跳出循环

{

break;

}

a[s] = a[i];

s = i;

}

a[s] = t;

}

 

//构建堆

//参数a：数组指针；参数n：数组有效值最大下标

void HeapSort(int * a, int len)

{

int i, j, k, t;

for(i = (len - 1) / 2; i >= 0; i--)

{

HeapAdjust(a, i, len);

}

for(i = len; i > 0; i--)

{

t = a[i];

a[i] = a[0];

a[0] = t;

HeapAdjust(a, 0, i-1);

}

}

 

#define MAXSIZE 100

#define MAXNUM 20

 

int main()

{

int i, j, k, list[MAXNUM]={};

int count = 0;

char str[MAXSIZE];

int time = 0;

printf("请输入你要输入的序列个数：");

scanf("%d",&k);

getchar();

for(i = 0; i < k; i++)

{

 

printf("请输入第%d个序列长度：",i+1);

scanf("%d",&list[i]);

}

 

HeapSort(list, k-1);

HeapSort(list, k-2);

for(i = k-2; i > 0; i--)

{

time++;

printf("第%d次合并为：长为%d的序列和长为%d的序列合并\n",time,list[i],list[i+1]);

list[i] = list[i] + list[i+1];

count += list[i] - 1;

 

HeapSort(list, i);

HeapSort(list, i-1);

}

time++;

printf("第%d次合并为：长为%d的序列和长为%d的序列合并\n",time,list[i],list[i+1]);

list[i] = list[i] + list[i+1];

count += list[i] - 1;

printf("比较的次数：%d\n",count);

return 0;

}

实验结果

 

1. 当输入的序列个数为5时

各序列长度分别为：4 3 2 5 1

达到预期效果

1. 当输入的序列个数为4时

各序列分别为：3 4 5 5

达到预期效果

1. 复杂度分析及算法改进

     (1)时间复杂度

算法中，n个序列需要进行n-1次比较，而每次比较需要进行两次堆调整找最小的元素，每趟堆调整的时间复杂度logn。

T（n）= O(n) * O(log(n));

所以

T（n）= O(nlog（n）)。

1. 空间复杂度

算法中，主要耗费空间的是存储各序列的数组和归并后的一个数组，m个序列总共有n个字节，所要耗费的空间就是2n。

所以s(n) = O(n);

1. 算法改进

可以进行三路（k路）最优合并，不知道会不会减少时间复杂度。