算法分析實(shí)驗(yàn)一實(shí)驗(yàn)報(bào)告冒泡,歸并排序

1/5.通過算法的程序?qū)崿F(xiàn)和執(zhí)行時(shí)間測(cè)試、并與理論上的結(jié)論進(jìn)行對(duì)比分析,深入理解算法時(shí)間復(fù)雜度分析中對(duì)于輸入數(shù)據(jù)考慮其等價(jià)類的意義,理解算法時(shí)間復(fù)雜度漸進(jìn)性態(tài)和和增長(zhǎng)率的概念,為后續(xù)學(xué)習(xí)和實(shí)驗(yàn)奠定基礎(chǔ),同時(shí)也學(xué)習(xí)程序效率測(cè)試的基本思路。<1>算法的計(jì)算時(shí)間取決于算法中某些操作的執(zhí)行次數(shù),這些操作是算法時(shí)間復(fù)雜度分<2>增長(zhǎng)率反映了算法的計(jì)算時(shí)間復(fù)雜度,即隨著算法輸入規(guī)模的增加、算法計(jì)算時(shí)間<3>算法的計(jì)算時(shí)間復(fù)雜度針對(duì)輸入數(shù)據(jù)的等價(jià)類來分析或測(cè)試。通過程序生成〔偽隨機(jī)數(shù),作為實(shí)驗(yàn)用測(cè)試數(shù)據(jù)?？墒褂镁幊陶Z言自帶的random函數(shù)2/5.生成,也可以采用一些有效的隨機(jī)數(shù)生成算法生成,例如"線性同余法",基于該算法,只要參數(shù)選擇合適,所產(chǎn)生的偽隨機(jī)數(shù)就能滿足均勻性和獨(dú)立性,與真正的隨機(jī)數(shù)具有相近的性質(zhì)。該數(shù),0a<m；c——增量,0c<m；X0——開始值,0X0<m。這樣得到所求的隨機(jī)數(shù)序列{Xi},稱作線形同余序列。用系統(tǒng)時(shí)間作為種子,首先生成隨機(jī)數(shù)組。再分別用冒泡排序和歸并排序法對(duì)生成的隨機(jī)數(shù)組排序。ayvoidmergeintvintleftintmidintright>//合并[left,mid]和[mid+1,right]{inti,j,k=0;i=left;j=mid+1;//i為第一路的下標(biāo)//j為第二路的下標(biāo)while<i<=mid&&j<=right>temp[k++]=<v[i]<=v[j]>?v[i++]:v[j++];ileimidtemp[k++]=v[i++];whilejrighttemp[k++]=v[j++];for<i=left,j=0;i<=right;++i,++j>v[i]=temp[j];}m{logn歸并logn歸并for<i=1;i<num;i*=2>{j=0;3/5.{j=right+1;}}//下標(biāo)不能溢出ayzprintf<"\n">;}{imeNULLintn;nfdnfor<inti=0;i<n;i++>{printf<"%d\n",array[i]>;//顯示生成的隨機(jī)數(shù)組}tnfor<intj=0;j<num;j++>{if<array[j]>array[j+1]>{wpse=1;}}}4/5.for<intk=0;k<n;k++>//顯示排好序的數(shù)組于屏幕printfd",array[k]>;printf<"\n">;}meNULLintn;nfdnfor<inti=0;i<n;i++>{printf<"%d\n",array[i]>;//顯示生成的隨機(jī)數(shù)組}(1)如代碼中所示,在比較循環(huán)中設(shè)置計(jì)數(shù)器count,每比較一次,則執(zhí)行count++,(2)兩次生成不同的100個(gè)隨機(jī)數(shù),采用冒泡排序的比較次數(shù)分別為：73次和97次。由此數(shù)據(jù)看出,輸入的數(shù)據(jù)不同,則采用相同算法排序所需的比較次數(shù)也會(huì)不同,即所需的時(shí)間會(huì)發(fā)生變化。因此,在比較不同算法的復(fù)雜度時(shí),應(yīng)當(dāng)選擇輸入相同的數(shù)據(jù)等價(jià)類,這樣才有可比性。(3)