計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)[王曉東][電子教案]第7章-在線瀏覽
2024-09-15 17:22本頁面
【正文】 設(shè) A是一個(gè)確定性算法，當(dāng)它的輸入實(shí)例為 x時(shí)所需的計(jì)算時(shí)間記為 tA(x)。希望獲得一個(gè)隨機(jī)化算法 B，使得對(duì)問題的輸入規(guī)模為 n的每一個(gè)實(shí)例均有 這就是舍伍德算法設(shè)計(jì)的基本思想。 )()( ntxt AA ??)()()( nsntxt AB ??9 舍伍德 (Sherwood)算法 復(fù)習(xí)學(xué)過的 Sherwood算法： （ 1）線性時(shí)間選擇算法 （ 2）快速排序算法 有時(shí)也會(huì)遇到這樣的情況，即所給的確定性算法無法直接改造成舍伍德型算法。例如，對(duì)于確定性選擇算法，可以用下面的洗牌算法 shuffle將數(shù)組 a中元素隨機(jī)排列，然后用確定性選擇算法求解。 templateclass Type void Shuffle(Type a[], int n) {// 隨機(jī)洗牌算法 static RandomNumber rnd。in。 Swap(a[i], a[j])。 ?如果用有序鏈表來表示一個(gè)含有 n個(gè)元素的有序集 S，則在最壞情況下，搜索 S中一個(gè)元素需要 ?(n)計(jì)算時(shí)間。在增設(shè)附加指針的有序鏈表中搜索一個(gè)元素時(shí)，可借助于附加指針跳過鏈表中若干結(jié)點(diǎn)，加快搜索速度。 ?應(yīng)在跳躍表的哪些結(jié)點(diǎn)增加附加指針以及在該結(jié)點(diǎn)處應(yīng)增加多少指針完全采用隨機(jī)化方法來確定。 11 跳躍表 在一般情況下，給定一個(gè)含有 n個(gè)元素的有序鏈表，可以將它改造成一個(gè)完全跳躍表，使得每一個(gè) k級(jí)結(jié)點(diǎn)含有 k+1個(gè)指針，分別跳過 2k1， 2k11， … ， 201個(gè)中間結(jié)點(diǎn)。這樣就可以在時(shí)間 O(logn)內(nèi)完成集合成員的搜索運(yùn)算。 完全跳躍表與完全二叉搜索樹的情形非常類似。集合元素的插入和刪除運(yùn)算會(huì)破壞完全跳躍表原有的平衡狀態(tài)，影響后繼元素搜索的效率。注意到在一個(gè)完全跳躍表中， 50%的指針是 0級(jí)指針； 25%的指針是 1級(jí)指針； … ； (100/2k+1)%的指針是 k級(jí)指針。另一方面，一個(gè) i級(jí)結(jié)點(diǎn)指向下一個(gè)同級(jí)或更高級(jí)的結(jié)點(diǎn)，它所跳過的結(jié)點(diǎn)數(shù)不再準(zhǔn)確地維持在 2i1。 13 跳躍表 在一個(gè)完全跳躍表中，具有 i級(jí)指針的結(jié)點(diǎn)中有一半同時(shí)具有 i+1級(jí)指針。為此目的，在插入一個(gè)新結(jié)點(diǎn)時(shí)，先將其結(jié)點(diǎn)級(jí)別初始化為 0，然后用隨機(jī)數(shù)生成器反復(fù)地產(chǎn)生一個(gè) [0， 1]間的隨機(jī)實(shí)數(shù) q。由此產(chǎn)生新結(jié)點(diǎn)級(jí)別的過程可知，所產(chǎn)生的新結(jié)點(diǎn)的級(jí)別為 0的概率為 1p，級(jí)別為 1的概率為p(1p)， … ，級(jí)別為 i的概率為 pi(1p)。為了避免這種情況，用 作為新結(jié)點(diǎn)級(jí)別的上界。當(dāng)前跳躍表中任一結(jié)點(diǎn)的級(jí)別不超過 np/1lognp/1log14 拉斯維加斯 ( Las Vegas )算法 拉斯維加斯算法的一個(gè)顯著特征是它所作的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。 while (!success) success=lv(x,y)。一個(gè)正確的拉斯維加斯算法應(yīng)該對(duì)所有輸入 x均有 p(x)0。由此容易想到下面的 拉斯維加斯算法 。 如果將上述隨機(jī)放置策略與回溯法相結(jié)合，可能會(huì)獲得更好的效果。隨機(jī)放置的皇后越多，后繼回溯搜索所需的時(shí)間就越少，但失敗的概率也就越大。關(guān)于整數(shù) n的因子分解問題是找出 n的如下形式的唯一分解式： 其中， p1p2…p k是 k個(gè)素?cái)?shù)， m1,m2,…,m k是 k個(gè)正整數(shù)。 給定一個(gè)合數(shù) n，求 n的一個(gè)非平凡因子的問題稱為整數(shù) n的因子分割問題。 for (int i=2。 i++) if
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1