实验4：递归与分治策略的应用

1、课程实验报告课程名称算法分析与设计班级实验日期姓名学号实验成绩实验名称实验4：递归与分治策略的应用实验目的及要求1掌握分治策略的基本步骤；2掌握分治策略的思想。实验环境操作系统：WindowsIDE：Visual C+实验内容（1）排序算法分别实现归并排序、快速排序和堆排序，输入规模N=64，128,256，512，（N取至单次排序运行时间不超过3分钟），输入数据随机生成1-10000之间的整数，记录实验结果，做出运行时间与输入规模之间的关系曲线图，说明算法的时间复杂度和空间复杂度，根据曲线图比较3种排序算法的优劣。（2）矩阵乘法调研Strassen矩阵乘算法，随机生成N*N的矩阵，矩阵中的每

2、个数字为1-100之间的整数，N=4,8,16（N取至单次矩阵乘时间不超过3分钟），分别用Strassen算法和你能想到的其它方法（例如直接计算）实现矩阵乘运算，做出运行时间与输入规模之间的关系曲线图，并简要分析Strassen算法和你所实现的方法的时间复杂度。调试过程及实验结果运行时截图：并归排序：运行到一定规模：快速排序：运行到一定规模：堆排序：运行到一定规模：矩阵乘法：1朴素算法：2Strassen矩阵乘算法一定规模后：总结横坐标计算规模：1：8129 2：65536 3： 4： 5：随着输入规模的增大，通过三种算法的时间记录做成折线图观察不难发现，在初期，三种算法所用时间几乎相等，随着

3、输入规模的不断增大，堆排序和快速排序仍然能够保持相对较小的增长，而并归排序所用时间复杂度开始大幅度增加。快速排序果然是快，数据越大优势越明显，并且实现上也较为简单。理论上它的平均时间和归并排序，堆排序都是一样的（在最坏情况还还不如它们），都是O(nlog2n)，但实际运行来看比它们两者的速度都快一倍以上。COOL！合并排序需要额外相同规模的数组，空间复杂度为O（n）。从具体实现来看，这只是一种理论上的优秀算法，想法比较简单直接，但实现上比quicksort复杂，运行时间也差，在数据很大的时候运行时间是heapsort的两倍，更不用说quicksort了。堆排序利用了二分树的结构，将时间复杂度降

4、到O(nlog2n),理论上和实现上表现都不错,并且发现在数据量是10000000时，甚至优于快排，可能是运行时数据的问题。对于strassen 算法对其时间复杂度分析：T（n）=7T(n/2)+O(n);而朴素算法的时间复杂度为n的三次方。随着数据增大，也出现乘方级别的时间复杂度差距。附录/头文件#include#include#include#include#include#define PARENT(i) (i/2) /几个较简单函数#define LEFT(i) (2*i+1)#define RIGHT(i) (2*i+2)using namespace std;/定义所需要变量等#d

5、efine MAX int aMAX; /数组存储原始顺序int tempMAX; /临时数组存储临时排序值int num; /计算统计逆序对数int N = 2; /数据规模clock_t begintimes, endtimes; /clock_t为clock()函数返回的变量类型double duration; /运行时间计算int heapsize; /堆长度/随机生成数函数int number()int a;a = rand() % 10000 + 1; /随机生成1到一万之间的整数return a;/初始化函数 对数组a初始化。void init()memset(temp,0, M

6、AX * sizeof(int); /临时数组清零for (int i = 0; i N; i+) /新数组赋值ai = number();return;/单次并归挑选void Merge(int left, int mid, int right) /需要三个参数，将原来数组分割int i = left, j = mid + 1, n = 0, length = right - left;/i开始为左半部分最左边，j为右半部分最左边while (i = mid & j aj) /左边比右边大tempn+ = aj+;num += mid - i + 1; /从i到mid都比aj大elsetem

7、pn+ = ai+;if (imid) /左边全部填满了，填右边while (j = right)tempn+ = aj+;else /右边填满，填左边while (i = mid)tempn+ = ai+;for (int k = 0; k = length; k+) /最后临时数组赋值到原数组aleft + k = tempk;/递归进行并归排序void MergeSort(int left, int right)if (leftright)int mid = (left + right) / 2;MergeSort(left, mid);MergeSort(mid + 1, right)

8、;Merge(left, mid, right);/快速排序一次int Partition(int left, int right)int i = left - 1;for (int j = left; j = right - 1; j+)if (aj aright) /把right作为轴i+; /这个i坐标左边的值是比aright小的swap(ai, aj); /交换swap(ai + 1, aright); /最后把i+1和right交换，这样轴就是i+1了必须是保证i+1上当初就是作为标杆的aright啊。return i + 1;/递归进行快排整体void QuickSort(int

9、left, int right)if (leftright)int q = Partition(left, right);QuickSort(left, q - 1);QuickSort(q + 1, right);/堆排序，函数太多，新建一个命名空间namespace MySorttemplate /堆排序的大顶堆优化（找数）void Max_Heapify(T*arr, int i, size_t heapSize)/从元素Ai、ALEFT(i)、ARIGHT(i)中找出最大的，并将其下标保存在Largest中/size_t heapSize = sizeof(arr) / sizeof(

10、*(arr); 也就是数量nint l = LEFT(i);int r = RIGHT(i);int largest;/寻找if (l*(arr + i)largest = l;elselargest = i;if (r*(arr + largest)largest = r;if (largest != i)swap(*(arr + i), *(arr + largest);Max_Heapify(arr, largest, heapSize);/如果Ai是最大的，则以i为根的子树已经是最大堆template /建立大顶堆，采用上面大顶堆方法进行优化void Build_Max_Heap(T*

11、arr, size_t heapSize) /从底部开始进行向上优化for (int i = heapSize / 2 - 1; i = 0; i-)Max_Heapify(arr, i, heapSize);template /获得最大顶堆，堆排序开始，即元素出堆void HeapSort(T *arr, size_t heapSize)Build_Max_Heap(arr, heapSize);for (int i = heapSize - 1; i 0; i-)swap(*arr, *(arr + i);Max_Heapify(arr, 0, i);int main()N = 2;doN

12、 *= 2; /依次增大计算规模srand(unsigned)time(NULL); /给一个时间种子init();/初始化一次cout 进行规模为 N 的排序 endl;cout 原始数组为：;for (int i = 0; i N; i+)cout ai ;cout endl;begintimes = clock(); /计时开始MergeSort(0,N-1);QuickSort(0,N-1);MySort:HeapSort(a, N);endtimes = clock(); /计时结束duration = 1000 * (double)(endtimes - begintimes) /

13、 CLK_TCK; /总共用时(毫秒)cout 排序后数组为：;for (int i = 0; i N; i+)cout ai ;cout endl;cout 此次用时为 duration 毫秒 endl endl endl;/记录实验结果，注意运行一次手动进行数据转移，清除数据FILE *fpWrite1 = fopen(data1.txt, a+); /记录实验结果fprintf(fpWrite1, %dn, N);fclose(fpWrite1);FILE *fpWrite2 = fopen(data2.txt, a+); /记录实验结果fprintf(fpWrite2, %dn, du

14、ration);fclose(fpWrite2); while (duration ); /单次时间小于3分钟return 0;#include#include#include#include#define MAX 10000using namespace std;int N;clock_t begintimes, endtimes; /clock_t为clock()函数返回的变量类型double duration; /运行时间计算/随机生成数函数int number()int a;a = rand() % 100 + 1; /随机生成1到一万之间的整数return a;/最朴素算法三重循环v

15、oid pusu(int *arr, int *brr, int *crr)for (int i = 0; i = N - 1; i+) for (int j = 0; j = N - 1; j+) for (int k = 0; k = N - 1; k+) crrij += arrik * brrkj;/Strassen矩阵乘法算法，矩阵分块，仅仅针对2的n次幂次阶处理void gerResultStrassen(int *arr, int *brr, int n, int *crr)if (n = 1)crr00 += arr00 * brr00;elseint m = n / 2;in

16、t *arr11 = new int*m;int *arr12 = new int*m;int *arr21 = new int*m;int *arr22 = new int*m;int *brr11 = new int*m;int *brr12 = new int*m;int *brr21 = new int*m;int *brr22 = new int*m;int *crr11 = new int*m;int *crr12 = new int*m;int *crr21 = new int*m;int *crr22 = new int*m;for (int i = 0; i m; +i)ar

17、r11i = new intm;arr12i = new intm;arr21i = new intm;arr22i = new intm;brr11i = new intm;brr12i = new intm;brr21i = new intm;brr22i = new intm;crr11i = new intm;crr12i = new intm;crr21i = new intm;crr22i = new intm;/获取矩阵/四块矩阵的分别计算/11for (int i = 0; i m; +i)for (int j = 0; j m; +j)arr11ij = arrij;brr1

18、1ij = brrij;/22for (int i = m; i n; +i)for (int j = m; j n; +j)arr22i - mj - m = arrij;brr22i - mj - m = brrij;/12for (int i = 0; i m; +i)for (int j = m; j n; +j)arr12ij - m = arrij;brr12ij - m = brrij;/21for (int i = m; i n; +i)for (int j = 0; j m; +j)arr21i - mj = arrij;brr21i - mj = brrij;for (in

19、t i = 0; i m; +i)for (int j = 0; j m; +j)crr11ij = 0;crr12ij = 0;crr21ij = 0;crr22ij = 0;/递归分治gerResultStrassen(arr11, brr11, m, crr11);gerResultStrassen(arr12, brr21, m, crr11);gerResultStrassen(arr11, brr12, m, crr12);gerResultStrassen(arr12, brr22, m, crr12);gerResultStrassen(arr21, brr11, m, crr

20、21);gerResultStrassen(arr22, brr21, m, crr21);gerResultStrassen(arr21, brr12, m, crr22);gerResultStrassen(arr22, brr22, m, crr22);/一下是矩阵的分为四块/11for (int i = 0; i m; +i)for (int j = 0; j m; +j)crrij += crr11ij;/22for (int i = m; i n; +i)for (int j = m; j n; +j)crrij += crr22i - mj - m;/12for (int i =

21、 0; i m; +i)for (int j = m; j n; +j)crrij += crr12ij - m;/21for (int i = m; i n; +i)for (int j = 0; j m; +j)crrij += crr12i - mj;/后期处理for (int i = 0; i m; +i)delete arr11i;delete brr11i;delete crr11i;delete arr12i;delete brr12i;delete crr12i;delete arr21i;delete brr21i;delete crr21i;delete arr22i;de

22、lete brr22i;delete crr22i;delete arr11;delete brr11;delete crr11;delete arr12;delete brr12;delete crr12;delete arr21;delete brr21;delete crr21;delete arr22;delete brr22;delete crr22;/初始化函数void init(int *arr, int *brr, int *crr)/初始化赋值for (int i = 0; i N; +i)for (int j = 0; j N; +j)arrij=number();crri

23、j = 0;for (int i = 0; i N; +i)for (int j = 0; j N; +j)brrij=number();/输出函数void input(int *arr, int *brr, int *crr)cout 矩阵An;for (int i = 0; i N; +i)for (int j = 0; j N; +j)cout arrij ;cout endl;cout 矩阵Bn;for (int i = 0; i N; +i)for (int j = 0; j N; +j)cout brrij ;cout endl;cout 相乘后的矩阵Cn;for (int i = 0; i N; +i)for (int j = 0; j N; +j)cout crrij