遞歸與分治策略的應(yīng)用

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)課程實(shí)驗(yàn)報(bào)告課程名稱(chēng)算法分析與設(shè)計(jì)班級(jí)實(shí)驗(yàn)日期姓名學(xué)號(hào)實(shí)驗(yàn)成績(jī)實(shí)驗(yàn)名稱(chēng)實(shí)驗(yàn)4：遞歸與分治策略的應(yīng)用實(shí)驗(yàn)?zāi)康募耙?掌握分治策略的基本步驟；2掌握分治策略的思想。實(shí)驗(yàn)環(huán)境操作系統(tǒng)：WindowsIDE：Visual C+實(shí)驗(yàn)內(nèi)容（1）排序算法分別實(shí)現(xiàn)歸并排序、快速排序和堆排序，輸入規(guī)模N=64，128,256，512，（N取至單次排序運(yùn)行時(shí)間不超過(guò)3分鐘），輸入數(shù)據(jù)隨機(jī)生成1-10000之間的整數(shù)，記錄實(shí)驗(yàn)結(jié)果，做出運(yùn)行時(shí)間與輸入規(guī)模之間的關(guān)系曲線(xiàn)圖，說(shuō)明算法的時(shí)間復(fù)雜度

2、和空間復(fù)雜度，根據(jù)曲線(xiàn)圖比較3種排序算法的優(yōu)劣。（2）矩陣乘法調(diào)研Strassen矩陣乘算法，隨機(jī)生成N*N的矩陣，矩陣中的每個(gè)數(shù)字為1-100之間的整數(shù)，N=4,8,16（N取至單次矩陣乘時(shí)間不超過(guò)3分鐘），分別用Strassen算法和你能想到的其它方法（例如直接計(jì)算）實(shí)現(xiàn)矩陣乘運(yùn)算，做出運(yùn)行時(shí)間與輸入規(guī)模之間的關(guān)系曲線(xiàn)圖，并簡(jiǎn)要分析Strassen算法和你所實(shí)現(xiàn)的方法的時(shí)間復(fù)雜度。調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果運(yùn)行時(shí)截圖：并歸排序：運(yùn)行到一定規(guī)模：快速排序：運(yùn)行到一定規(guī)模：堆排序：運(yùn)行到一定規(guī)模：矩陣乘法：1樸素算法：2Strassen矩陣乘算法一定規(guī)模后：總結(jié)橫坐標(biāo)計(jì)算規(guī)模：1：8129 2：655

3、36 3： 4： 5：隨著輸入規(guī)模的增大，通過(guò)三種算法的時(shí)間記錄做成折線(xiàn)圖觀察不難發(fā)現(xiàn)，在初期，三種算法所用時(shí)間幾乎相等，隨著輸入規(guī)模的不斷增大，堆排序和快速排序仍然能夠保持相對(duì)較小的增長(zhǎng)，而并歸排序所用時(shí)間復(fù)雜度開(kāi)始大幅度增加?？焖倥判蚬皇强欤瑪?shù)據(jù)越大優(yōu)勢(shì)越明顯，并且實(shí)現(xiàn)上也較為簡(jiǎn)單。理論上它的平均時(shí)間和歸并排序，堆排序都是一樣的（在最壞情況還還不如它們），都是O(nlog2n)，但實(shí)際運(yùn)行來(lái)看比它們兩者的速度都快一倍以上。COOL！合并排序需要額外相同規(guī)模的數(shù)組，空間復(fù)雜度為O（n）。從具體實(shí)現(xiàn)來(lái)看，這只是一種理論上的優(yōu)秀算法，想法比較簡(jiǎn)單直接，但實(shí)現(xiàn)上比quicksort復(fù)雜，運(yùn)行時(shí)間

4、也差，在數(shù)據(jù)很大的時(shí)候運(yùn)行時(shí)間是heapsort的兩倍，更不用說(shuō)quicksort了。堆排序利用了二分樹(shù)的結(jié)構(gòu)，將時(shí)間復(fù)雜度降到O(nlog2n),理論上和實(shí)現(xiàn)上表現(xiàn)都不錯(cuò),并且發(fā)現(xiàn)在數(shù)據(jù)量是10000000時(shí)，甚至優(yōu)于快排，可能是運(yùn)行時(shí)數(shù)據(jù)的問(wèn)題。對(duì)于strassen 算法對(duì)其時(shí)間復(fù)雜度分析：T（n）=7T(n/2)+O(n);而樸素算法的時(shí)間復(fù)雜度為n的三次方。隨著數(shù)據(jù)增大，也出現(xiàn)乘方級(jí)別的時(shí)間復(fù)雜度差距。附錄/頭文件#include#include#include#include#include#define PARENT(i) (i/2) /幾個(gè)較簡(jiǎn)單函數(shù)#define LEFT(i)

5、 (2*i+1)#define RIGHT(i) (2*i+2)using namespace std;/定義所需要變量等#define MAX int aMAX; /數(shù)組存儲(chǔ)原始順序int tempMAX; /臨時(shí)數(shù)組存儲(chǔ)臨時(shí)排序值int num; /計(jì)算統(tǒng)計(jì)逆序?qū)?shù)int N = 2; /數(shù)據(jù)規(guī)模clock_t begintimes, endtimes; /clock_t為clock()函數(shù)返回的變量類(lèi)型double duration; /運(yùn)行時(shí)間計(jì)算int heapsize; /堆長(zhǎng)度/隨機(jī)生成數(shù)函數(shù)int number()int a;a = rand() % 10000 + 1; /隨

6、機(jī)生成1到一萬(wàn)之間的整數(shù)return a;/初始化函數(shù) 對(duì)數(shù)組a初始化。void init()memset(temp,0, MAX * sizeof(int); /臨時(shí)數(shù)組清零for (int i = 0; i N; i+) /新數(shù)組賦值ai = number();return;/單次并歸挑選void Merge(int left, int mid, int right) /需要三個(gè)參數(shù)，將原來(lái)數(shù)組分割int i = left, j = mid + 1, n = 0, length = right - left;/i開(kāi)始為左半部分最左邊，j為右半部分最左邊while (i = mid & j

7、aj) /左邊比右邊大tempn+ = aj+;num += mid - i + 1; /從i到mid都比aj大elsetempn+ = ai+;if (imid) /左邊全部填滿(mǎn)了，填右邊while (j = right)tempn+ = aj+;else /右邊填滿(mǎn)，填左邊while (i = mid)tempn+ = ai+;for (int k = 0; k = length; k+) /最后臨時(shí)數(shù)組賦值到原數(shù)組aleft + k = tempk;/遞歸進(jìn)行并歸排序void MergeSort(int left, int right)if (leftright)int mid = (l

8、eft + right) / 2;MergeSort(left, mid);MergeSort(mid + 1, right);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+; /這個(gè)i坐標(biāo)左邊的值是比aright小的swap(ai, aj); /交換swap(ai + 1, aright); /最后把i+1和right交換，這樣軸就是i+1了必須是保

9、證i+1上當(dāng)初就是作為標(biāo)桿的aright啊。return i + 1;/遞歸進(jìn)行快排整體void QuickSort(int left, int right)if (leftright)int q = Partition(left, right);QuickSort(left, q - 1);QuickSort(q + 1, right);/堆排序，函數(shù)太多，新建一個(gè)命名空間namespace MySorttemplate /堆排序的大頂堆優(yōu)化（找數(shù)）void Max_Heapify(T*arr, int i, size_t heapSize)/從元素Ai、ALEFT(i)、ARIGHT(i)

10、中找出最大的，并將其下標(biāo)保存在Largest中/size_t heapSize = sizeof(arr) / sizeof(*(arr); 也就是數(shù)量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是最大的，則以

11、i為根的子樹(shù)已經(jīng)是最大堆template /建立大頂堆，采用上面大頂堆方法進(jìn)行優(yōu)化void Build_Max_Heap(T*arr, size_t heapSize) /從底部開(kāi)始進(jìn)行向上優(yōu)化for (int i = heapSize / 2 - 1; i = 0; i-)Max_Heapify(arr, i, heapSize);template /獲得最大頂堆，堆排序開(kāi)始，即元素出堆void HeapSort(T *arr, size_t heapSize)Build_Max_Heap(arr, heapSize);for (int i = heapSize - 1; i 0; i-)s

12、wap(*arr, *(arr + i);Max_Heapify(arr, 0, i);int main()N = 2;doN *= 2; /依次增大計(jì)算規(guī)模srand(unsigned)time(NULL); /給一個(gè)時(shí)間種子init();/初始化一次cout 進(jìn)行規(guī)模為 N 的排序 endl;cout 原始數(shù)組為：;for (int i = 0; i N; i+)cout ai ;cout endl;begintimes = clock(); /計(jì)時(shí)開(kāi)始MergeSort(0,N-1);QuickSort(0,N-1);MySort:HeapSort(a, N);endtimes = cl

13、ock(); /計(jì)時(shí)結(jié)束duration = 1000 * (double)(endtimes - begintimes) / CLK_TCK; /總共用時(shí)(毫秒)cout 排序后數(shù)組為：;for (int i = 0; i N; i+)cout ai ;cout endl;cout 此次用時(shí)為 duration 毫秒 endl endl endl;/記錄實(shí)驗(yàn)結(jié)果，注意運(yùn)行一次手動(dòng)進(jìn)行數(shù)據(jù)轉(zhuǎn)移，清除數(shù)據(jù)FILE *fpWrite1 = fopen(data1.txt, a+); /記錄實(shí)驗(yàn)結(jié)果fprintf(fpWrite1, %dn, N);fclose(fpWrite1);FILE *fp

14、Write2 = fopen(data2.txt, a+); /記錄實(shí)驗(yàn)結(jié)果fprintf(fpWrite2, %dn, duration);fclose(fpWrite2); while (duration ); /單次時(shí)間小于3分鐘return 0;#include#include#include#include#define MAX 10000using namespace std;int N;clock_t begintimes, endtimes; /clock_t為clock()函數(shù)返回的變量類(lèi)型double duration; /運(yùn)行時(shí)間計(jì)算/隨機(jī)生成數(shù)函數(shù)int number(

15、)int a;a = rand() % 100 + 1; /隨機(jī)生成1到一萬(wàn)之間的整數(shù)return a;/最樸素算法三重循環(huán)void 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矩陣乘法算法，矩陣分塊，僅僅針對(duì)2的n次冪次階處理void gerResultStrassen(int *arr, int *brr, int n,

16、 int *crr)if (n = 1)crr00 += arr00 * brr00;elseint m = n / 2;int *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 *crr2

17、1 = new int*m;int *crr22 = new int*m;for (int i = 0; i m; +i)arr11i = 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;/獲取矩陣/四塊矩陣的分別計(jì)算/11for (

18、int i = 0; i m; +i)for (int j = 0; j m; +j)arr11ij = arrij;brr11ij = 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

19、 j = 0; j m; +j)arr21i - mj = arrij;brr21i - mj = brrij;for (int 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

20、(arr12, brr22, m, crr12);gerResultStrassen(arr21, brr11, m, crr21);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)f

21、or (int j = m; j n; +j)crrij += crr22i - mj - m;/12for (int i = 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 cr

22、r12i;delete arr21i;delete brr21i;delete crr21i;delete arr22i;delete 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;/初始化函數(shù)void init(int *arr, int *brr, int *crr)/初始化賦值for

23、(int i = 0; i N; +i)for (int j = 0; j N; +j)arrij=number();crrij = 0;for (int i = 0; i N; +i)for (int j = 0; j N; +j)brrij=number();/輸出函數(shù)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