舍伍德演算法c

⑴ 哪位大神能指教下MO的排序問題

1.出現的問題是如果本來是順序或倒序，那麼排序的時間最長
排序的次數與初始排序序列有關，
修正方法:
加個隨機函數，隨機選擇一個數與第一個數交換，把該數作為一個分區元素
這句是舍伍德演算法
2.
排序的次數與初始排序序列有關.
3.
nlog(n)

⑵ 舍伍德演算法的基本思想

設A是一個確定性演算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設Xn是演算法A的輸入規模為n的實例的全體，則當問題的輸入規模為n時，演算法A所需的平均時間為這顯然不能排除存在x∈Xn使得 tA(x)>>tA(n)的可能性。
希望獲得一個概率演算法B，使得對問題的輸入規模為n的每一個實例均有
這就是舍伍德演算法設計的基本思想。當s(n)與tA(n)相比可忽略時，舍伍德演算法可獲得很好的平均性能。
舍伍德演算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性演算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定演算法中引入隨機性將它改造成一個舍伍德演算法，消除或減少問題的好壞實例間的這種差別。舍伍德演算法精髓不是避免演算法的最壞情況行為，而是設法消除這種最壞行為與特定實例之間的關聯性。

⑶ 有哪些隨機數演算法呢

1、數值概率演算法：用於數值問題的求解。所得到的解幾乎都是近似解，近似解的精度
隨著計算時間的增加而不斷地提高。
2、拉斯維加斯演算法（LasVegas）：要麼給出問題的正確答案，要麼得不到答案。反復求解多次，可
使失效的概率任意小。
3、蒙特卡羅演算法（MonteCarlo）：總能得到問題的答案，偶然產生不正確的答案。重復運行，每一次
都進行隨機選擇，可使不正確答案的概率變得任意小。
4、舍伍德演算法（Sherwood）：很多具有很好的平均運行時間的確定性演算法，在最壞的情況下性能很
壞。引入隨機性加以改造，可以消除或減少一般情況和最壞情況的差別。

⑷ 舍伍德演算法的3數組實現鏈表

在不包含指針的程序沒汁語言如VB中，可以採用數組來實現鏈表，實現了「虛假」的指針操作。但就是這種「虛假」指針，恰恰不僅彌補某些指針的某些缺結，還發揮了這種「虛假」指針的優點。採用這種數據結構，拋棄了順序存儲在插入運算中需要移動大量元素的缺點。採用這種數據結構，利用,舍伍德演算法進行查找、插入和刪除操作，其效率在傳統的順序存儲和鏈式存儲之間。
在所有的程序設計語言中都有數組，可以利用兩個數組
m_pData和m_pLink來表示所給的含有多個元素的有序集。用m_pData存儲有序鏈表的數據，用m_pLink存儲有序鏈表的數據元索的直接後繼的指針(在數組中的索引號)。m_pLink[O]指向有序鏈表的第一個元素，換句話說，m_pData[m_plink[0]]是有序鏈表中的最小元素。一般來說，如果m_pData[i】是有序鏈表中的第k個元素，則m_pData[m_plink[i]]是有序鏈表中的第k+1個元素。有序鏈表的有序性表現在：對於任意的I≤i≤n，有m_pData[i]≤m_pData[m_plink[i]]。有序鏈表中的最大元素m_pData[k]有m_plink[k]-O(無後繼，指向第零個結點，第零個結點是監視哨)且m_pDaIa[0]為一個大數。
倘若採用順序搜索的方式在這種有序鏈表中查找指定的元素，每次查找與有序鏈表建立的順序有關，此時採用舍伍德演算法可以消除這種聯系。
利用數組下標的索引性質，可以設計一個隨機化的搜索演算法，以改進搜索的時間復雜性。該演算法的基本思想是隨機選取數組元素若干次，從較接近搜索元素x的位置開始進行順序查找，而沒有必要從有序鏈表的開始位置進行搜索，從而較大幅度地提高查找效率。
遺憾的是在STL容器類中的Voctor類採用順序存儲，List類採用鏈式存儲，並沒有這樣的一種數據結構一用數組模擬有序鏈表。模仿標准STL中的類模板的實現，我們編制了一個類模板COrderList，並實現了用舍伍德演算法進行查找、插入等演算法。

⑸ 重精解除率怎麼算

1）數值概率演算法：常用於數值問題的求解，得到的往往是近似解（1）解的精度隨計算時間的增加而提高（2）在許多情況下，計算出問題的精確解是不可能或沒必要 2）蒙特卡羅演算法：用於求解問題的准確解，可以求得問題的一個解，但該解未必正確（1）求得正確解的概率依賴於演算法的計算時間多次執行蒙特卡羅演算法，可以提高獲得正確解的概率（2）無法有效判定所得到的解是否肯定正確。 3）拉斯維加斯演算法：不會得到不正確的解（1）有時找不到問題的解（2）找到正確解的概率隨演算法計算時間的增加而提高（3）用同一拉斯維加斯演算法反復對問題實例求解足夠多次，可使求解失敗的概率任意小。 4）舍伍德演算法：總能求解得到問題的一個解，而且所求得得解總是正確的。將確定性演算法引入隨機性改造成舍伍德演算法，可消除或減少問題對於好壞實例間的差別。

⑹ 舍伍德演算法總能得到問題的一個正確解嗎

1.出現的問題是如果本來是順序或倒序，那麼排序的時間最長排序的次數與初始排序序列有關，修正方法:加個隨機函數，隨機選擇一個數與第一個數交換，把該數作為一個分區元素這句是舍伍德演算法2.排序的次數與初始排序序列有關.3.nlog(n)

⑺ 演算法具有確定性,因此在寫演算法中一定不能包含隨機數調用的函數

錯的，這里舉個例子吧：隨機快速排序，每次隨機取一個值作為排序分類標准把當前區間拆成兩部分，但是最後它還是會排好序，是一個具有確定結果的演算法，只是得到結果的過程隨機。
希望能幫到你。

⑻ 舍伍德演算法的4用類模板實現演算法

用類模板實現的演算法如下：
template<classType>
boolCOrderlist<Type>：：Search(Type x, int&index)
//搜索有序鏈襲中的指定元素x、並將其位置放在index變數中
{//mCnrrentNumber為當前有序鏈表中元素的個數，它為類模
//板CorderLisl的數據成員,m為隨機搜索的次數；
int m=(int)sqrt(double(m_CurmntNumber));
int j;
index=O;
//m_LowBound為當前有序鏈表中最小元素的值．它為類模板
//CorderList的數據成員;
Type max=m_LowBound;
for(int i=l；i<=m，i++}
{j=randl();
//產生一個隨機數j，在數組m_pData[]隨機中找一個值
Type y-m—pDataU]：
If((max<y)&&(y<x))
//找最靠近查找元素x的索引位置Index
{max=y；
index=j；}
}
//從最靠近查找元素x的Index所指向的位置升妯進行順序搜索
while(m_pData[m_pLink[index]]<x)
index=m_pLink[index]；∥指針後移
return(n_pData[m_pLink[indcx]==x)；//是否找到
}