算法設(shè)計與分析 課件 9.1-概率算法 - 引例 - 主元素求解

算法設(shè)計與分析概率算法-引例信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)1,2,2,3,2,4,2,4,2,2假設(shè)一定存在主元素方法一：排序，位置5的數(shù)即為主元素1222222344求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2方法二：士兵守陣地，留下的士兵就是主元素1223242422VS求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS1223242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS1223242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS23242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS23242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS23242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS2422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS2422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS2422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS22求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS22求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS22求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法三：上帝扔骰子，選擇后再判斷1223242422123456789103求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2方法三：上帝扔骰子，選擇后再判斷1223242422123456789102求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)方法三：上帝投色子方法二：士兵守陣地方法一：排序確定算法概率算法允許算法執(zhí)行過程中隨機地選擇計算步驟，因此算法的每一次執(zhí)行過程可能都不完全相同。算法的每一計算步驟都是確定的，在輸入不變的情況下，不管重復(fù)執(zhí)行算法多少次，其結(jié)果都完全相同。確定算法：遞歸、分治、動規(guī)、貪心、搜索概率算法測試選擇題：本節(jié)課針對主元素求解問題給出的三種方法：排序法，士兵守陣地和概率算法，三種算法在平均情況下需要的計算次數(shù)分別表示為W1，W2和W3，三者從大到小排序正確的是（）A：W1，W2，W3