算法設(shè)計與分析之二 蠻力法

目錄

---

1.蠻力法的設(shè)計思想
2.蠻力法優(yōu)點(diǎn)
3. 冒泡排序分析
4. 選擇排序分析
5. 蠻力法中冒泡排序與選擇排序的時間空間復(fù)雜度分析
6. 蠻力法C語言實現(xiàn)
7. 算法穩(wěn)定性的問題
8. 百錢買百雞的問題
9. 補(bǔ)充：雞尾酒排序法
10.蠻力法的思考

---

作為算法設(shè)計技術(shù)中最簡單的一種設(shè)計策略，蠻力法從最先開始接觸編程語言時就一直伴隨著我們。

1. 蠻力法的設(shè)計思想

課本上的定義：蠻力法是指一種簡單直接

1.蠻力法又稱為枚舉法，窮舉法，暴力法。
2.蠻力法是指采用遍歷（掃描）技術(shù)，即采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解。依次處理所有元素是蠻力法的關(guān)鍵，為了避免陷入重復(fù)試探，應(yīng)保證處理過的元素不再被處理。

蠻力法解決問題的方法

根據(jù)問題中的條件將可能的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解。但有時一一列舉出的情況數(shù)目很大，如果超過了我們所能忍受的范圍，則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數(shù)目。

蠻力法解決問題的算法設(shè)計：

1）找出枚舉范圍：分析問題所涉及的各種情況。
2）找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達(dá)式表示。

2.蠻力法優(yōu)點(diǎn)

---

邏輯清晰，編寫程序簡潔

對于一些重要的問題（比如：排序、查找、矩陣乘法和字符串匹配），可以產(chǎn)生一些合理的算法

解決問題的實例很少時，可以花費(fèi)較少的代價

可以解決一些小規(guī)模的問題（使用優(yōu)化的算法沒有必要，而且某些優(yōu)化算法本身較復(fù)雜)

可以作為其他高效算法的衡量標(biāo)準(zhǔn)

---

3. 冒泡排序分析（穩(wěn)定性排序方法）

第i趟排序?qū)π蛄械那皀-i+1個元素從第一個元素開始依次作如下操作:相鄰的兩個元素比較大小，若前者大于后者,則兩個元素交換位置，否則不交換位置。該n-i+1個元素中最大值元素移到該n-i+1個元素的最后。冒泡排序方法比較適合于參加排序的序列的原始狀態(tài)基本有序的情況。

4. 選擇排序分析（非穩(wěn)定性排序方法）

選擇排序開始的時候，掃描整個序列，找到整個序列的最小記錄和序列中的第一個記錄交換，從而將最小記錄放到它在有序區(qū)的最終位置上，然后再從第二個記錄開始掃描序列，找到n-1個序列中的最小記錄，再和第二個記錄交換位置。一般地，第i趟排序從第i個記錄開始掃描序列，在n-i+1（1≤i≤n-1）個記錄中找到關(guān)鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。
每一趟排序從序列中未排序的元素中選擇一個值最小的元素，將其置于沒有排好序的元素的最前面。已排好序的元素不必交換。

5. 蠻力法中冒泡排序與選擇排序的時間空間復(fù)雜度分析

1.選擇排序：

平均時間復(fù)雜度o(n^2 )
最好時間復(fù)雜度o(n^2 )
最壞時間復(fù)雜度o(n^2 )
空間復(fù)雜度o(1)

2.冒泡排序：

平均時間復(fù)雜度o(n^2 )
最好時間復(fù)雜度o(n)
最壞時間復(fù)雜度o(n^2 )
空間復(fù)雜度o(1)

6.1蠻力法中冒泡排序C語言實現(xiàn)

#include <stdio.h> void maopaopaixu(int s[],int n); void main() {int s[20];int i;int n;printf("請輸入要輸入的個數(shù)：");scanf("%d",&n);printf("請輸入要排序的序列：\n");for (i = 0; i < n; i++){scanf("%d",&s[i]);}maopaopaixu(s,n);printf("排序后的序列：\n");for (i = 0; i < n; i++){printf("%d\t",s[i]);} } void maopaopaixu(int s[],int n) {int i, j;int temp;for(i = 0; i < n; i++){for (j = 0; j < n-1; j++){if(s[i] < s[j]){temp = s[i];s[i] = s[j];s[j] = temp;}}} }

6.2蠻力法中選擇排序C語言實現(xiàn)

#include <stdio.h> void suanzepaixu(int s[],int n); void main() {int n;int i;int s[20];printf("請輸入要輸入的個數(shù)");scanf("%d",&n);printf("請輸入要排序的數(shù)據(jù)\n");for(i = 0; i < n; i++){scanf("%d",&s[i]);}suanzepaixu(s,n);for (i = 0; i < n; i++){printf("%d\t",s[i]);} } void suanzepaixu(int s[],int n) {int i,j;int k;int temp;for (i = 0; i < n; i++){k = i;for(j = i + 1; j < n; j++){if(s[j] < s[k]){k = j;}}if(k != i){temp = s[k];s[k] = s[i];s[i] = temp;}} }

7.算法穩(wěn)定性的問題

冒泡排序：

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間。所以，如果兩個元素相等，不用交換；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。

選擇排序：

選擇排序即掃描整個序列，找到整個序列的最小記錄和序列中的第一個記錄交換，從而將最小記錄放到它在有序區(qū)的最終位置上，然后再從第二個記錄開始掃描序列，找到n-1個序列中的最小記錄，再和第二個記錄交換位置。一個序列當(dāng)如果當(dāng)前元素比一個元素小，而該小的元素又出現(xiàn)在一個和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。因此選擇排序是非穩(wěn)定性的。

8.百錢買百雞問題

數(shù)學(xué)家張丘建提出百雞百錢問題，今有雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一。百錢買百雞，問雞翁，雞母，雞雛各幾何？翻譯后：設(shè)雞翁，雞母，雞雛分別為x,y,z，給出一百錢要買百雞。如果全買公雞最多買20只，顯然x在0—20之間，同理y的取值在0-33之間，所以根據(jù)分析，不難用枚舉法求出問題的所有符合情況的解。
這是個經(jīng)典問題，從我們學(xué)數(shù)學(xué)就避不開的問題，用蠻力法實現(xiàn)應(yīng)該是最不費(fèi)腦筋的。首先，簡單分析一下枚舉范圍，都買公雞最多二十只，x的范圍0-20，都買母雞最多30只，y的范圍0-30。

#include <stdio.h> //雞翁x,雞母y,雞雛z void main() {int z = 0;int x, y;//雞翁的數(shù)量變化范圍for (x= 0; x < 20; x++){//雞母的數(shù)量變化范圍for (y = 0; y < 33; y++){z = 100 - x - y;//雞雛的受制約范圍if (z % 3 == 0 && 5 * x + 3 * y + z / 3 == 100){printf("x = %d,y = %d,z = %d\n",x,z,y);}}} }

9.雞尾酒排序

---

雞尾酒排序法，又名雙向冒泡排序法，算法傳統(tǒng)冒泡法的一點(diǎn)改進(jìn)。但是對于雞尾酒排序，算法的時間復(fù)雜度與空間復(fù)雜度并沒有改進(jìn)。
　　不同的是排序的交換次數(shù)。某些情況下雞尾酒排序比普通冒泡排序的交換次數(shù)少。比如{2,3,4,1},雞尾酒排序只需交換2次，而冒泡排序需要三次。總體上，雞尾酒排序可以獲得比冒泡排序稍好的性能。但是完全逆序時，雞尾酒排序與冒泡排序的效率都非常差。
　　雞尾酒排序的思想就是在從前往后依次循環(huán)依靠鄰近數(shù)據(jù)交換實現(xiàn)結(jié)果的同時，依次從后往前循環(huán)數(shù)據(jù)交換。前者交換獲取未排序最大值，而后者交換獲取未排序最小值。實現(xiàn)過程如下圖：
　　
　　

---

python代碼

l = [2,3,4,1,90,6] size = len(l) sign = 1 for i in range(int(size / 2)):if sign:sign = 0for j in range(i, size - 1 - i):if l[j] > l[j + 1]:l[j], l[j + 1] = l[j + 1], l[j]for k in range(size - 2 - i, i, -1):if l[k] < l[k - 1]:l[k], l[k - 1] = l[k - 1], l[k]sign = 1 else:break print(l)

10.蠻力法的思考

用蠻力法設(shè)計的算法，一般來說，經(jīng)過適度的努力后，都可以對算法的第一個版本進(jìn)行一定程度的改良，改進(jìn)其時間性能，但只能減少系數(shù)，而數(shù)量級不會改變。

總結(jié)

以上是生活随笔為你收集整理的算法分析学习笔记二 蛮力法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。