算法設(shè)計(jì)與分析第七章隨機(jī)算法及計(jì)算復(fù)雜性-文庫吧資料
2025-01-12 18:36本頁面
【正文】 s,i,j,k。 ? 連續(xù)運(yùn)行 k次，返回的概率減少為 2k，算法錯(cuò)誤的概率為 2k 。} else return FALSE。 if (kn/2) {x = A[i]。jn。 k = 0。 random_seed(0)。 蒙特卡羅（ Monte Carlo）算法 ? 算法 求數(shù)組 A的主元素 ? 輸入： n個(gè)元素的數(shù)組 A[] ? 輸出： 數(shù)組 A的主元素 BOOL majority(Type A[],Type amp。 ?元素比較次數(shù)為 。 二、一般方法 ?每個(gè)元素和其它元素比較，并計(jì)數(shù)。 蒙特卡羅（ Monte Carlo）算法 ? 數(shù)組的主元素問題 一、問題 ? n個(gè)元素的數(shù)組 A， A中元素 x，若 A中一半以上元素與 x相同，稱 x是 A的主元素。如果一個(gè)蒙特卡羅算法對于問題的任一實(shí)例得到正確解的概率不小于 p，則稱該蒙特卡羅算法是 p正確的，且稱 p1/2是該算法的優(yōu)勢。 2)12(2nnn ? 蒙特卡羅（ Monte Carlo）算法 ? 蒙特卡羅算法則在一般情況下可以保證對問題的所有實(shí)例都以高概率給出正確解，但是通常無法判定一個(gè)具體解是否正確。 ? 算法在前 calogn(c為固定常數(shù) )次迭代內(nèi)不退出的概率 (4/5) calogn=ncalog(4/5),若取 c ≥ 1/log(5/4),則其值 na, ? 因此，算法在 calogn次迭代以內(nèi)終止的概率 ≥ 1 na。(a[i]==a[j])) return(i)。 if((i!=j)amp。 拉斯維加斯（ Las Vegas）算法 ? 拉斯維加斯（ Las Vegas）算法 – int RepeatedElement(Type a[],int n){ while (1){ int i=random()%n+1。問題是要識別重復(fù)的元素。 ? k充分大， (1 δ )k趨于 0。 拉斯維加斯（ Las Vegas）算法 ? p(x)：對輸入實(shí)例成功地運(yùn)行 las_vegas的概率 ? 若存在常數(shù) δ0，使得對的所有實(shí)例 p，都有p(x)= δ ，則失敗的概率小于 1 δ 。 拉斯維加斯算法反復(fù)地運(yùn)行下面的代碼段： while(!las_vegas(P(x))) 。 BOOL las_vegas()：解問題的某個(gè)實(shí)例的代碼段。 /* 排序第二個(gè)子數(shù)組 */ ? 10. } ? 11. } ? 算法的期望運(yùn)行時(shí)間是 。 /* 按元素 A[low]把數(shù)組劃分為兩個(gè) */ ? 8. r_quicksort(A,low,k1)。/* 產(chǎn)生 low到 high之間的隨機(jī)數(shù) k */ ? 6. swap(A[low],A[k])。 /* 遞歸調(diào)用隨機(jī)快速排序算法 */ ? 6. } 舍伍德 (Sherwood)算法 ? 1. void r_quicksort(Type A[],int low,int high) ? 2. { ? 3. int k。時(shí)間復(fù)雜性與確定性算法的時(shí)間復(fù)雜性相當(dāng) . )()()( nsnTxT AB ??||/)()( nXx BB XxTnTn???)()()( nsnTnT AB ??)(nTA 舍伍德 (Sherwood)算法 ? 隨機(jī)快速排序算法 ? 算法 隨機(jī)選擇樞點(diǎn)的快速排序算法 ? 輸入： 數(shù)組 A,數(shù)組元素的的起始位置 low,終止位置 high ? 輸出： 按非降順序排序的數(shù)組 A ? 1. template class Type ? 2. void quicksort_random(Type A[],int low,int high) ? 3. { ? 4. random_seed(0)。 ? 當(dāng)輸入數(shù)據(jù)按遞增或遞減順序排列時(shí)，算法的運(yùn)行時(shí)間變壞 ||/)()( nXxAA XxTnTn???nXx? )()( nTxT A
電大資料相關(guān)推薦
鄂ICP備17016276號-1