算法小结 之 蛮力法
文章目錄
- 1.1 蠻力法的定義
- 1.2 蠻力法的優缺點
- 1.3 蠻力法的設計思想
- 1.4 蠻力法的經典使用
- 1.4.1 排序
- 1.4.1.1選擇排序
- 1.4.1.2冒泡排序
- 1.4.1.3 順序查找
- 1.4.2 字符串匹配問題
- 1.4.3 最近點對的蠻力算法
- 1.4.4 凸包問題的蠻力算法
- 1.4.5 窮舉法
- 1.4.5.1 NP難問題
- 1.4.5.2 TSP問題
- 1.4.5.3 背包問題
- 1.4.5.4 分配問題
1.1 蠻力法的定義
?蠻力法又稱為枚舉法，窮舉法，暴力法。蠻力算法是一種簡單直接地解決問題，但不一定是最高效的方法
1.2 蠻力法的優缺點
蠻力法所具有的優點：
蠻力法所具有的缺點：
1.3 蠻力法的設計思想
蠻力法是指采用遍歷（掃描）技術，即采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解。依次處理所有元素是蠻力法的關鍵，為了避免陷入重復試探，應保證處理過的元素不再被處理。
1.4 蠻力法的經典使用
1.4.1 排序
1.4.1.1選擇排序
問題描述：
? 給定一個可排序的n元序列，將它們按照非降序方法重新排序
使用蠻力法的思路（遞歸描述）：
算法設計（偽代碼）：
//非遞歸 Algorithm SS(A[0..n-1]) //SelectionSort//輸入：n元數組//輸出：n元數組for i=0 to n-2 domin:=i;for j:=i+1 to n-1 doif A[j]<A[min] then min->j;swap A[i] and A[min]算法分析：
-
輸入規模（空間復雜度）
因為輸入的是n元數組，故空間復雜度是：O(n)
-
算法的基本操作：
比較A[j] < A[min]，數據交換swap
-
比較次數C(n)
C(n)=∑i=0n?2∑j=i+1n?11=∑i=0n?2(n?1?i)=n(n?1)2C(n)={\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}1}={\sum_{i=0}^{n-2}(n-1-i)}=\frac{n(n-1)}{2} C(n)=i=0∑n?2?j=i+1∑n?1?1=i=0∑n?2?(n?1?i)=2n(n?1)?
于是C(n)屬于O（n2）
1.4.1.2冒泡排序
問題描述：
? 給定一個可排序的n元序列，將它們按照非降序方法重新排序
使用蠻力法的解決思路：
算法設計：
Algorithm BS(A[0..n-1]) //BubbleSort//輸入：n元數組//輸出：n元數組for i:=0 to n-2 dofor j:=0 to n-2-i doif A[j+1]<A[j] then swap A[j] and A[j+1]算法分析：
-
輸入規模（空間復雜度）
因為輸入的是n元數組，故空間復雜度是：O(n)
-
算法的基本操作：
比較A[j] < A[j+1]，數據交換swap
-
比較次數C(n)
C(n)=∑i=0n?2∑j=0n?2?i1=∑i=0n?2(n?1?i)=n(n?1)2C(n)={\sum_{i=0}^{n-2}\sum_{j=0}^{n-2-i}1}={\sum_{i=0}^{n-2}(n-1-i)}=\frac{n(n-1)}{2} C(n)=i=0∑n?2?j=0∑n?2?i?1=i=0∑n?2?(n?1?i)=2n(n?1)?
于是C(n)屬于O（n2）
1.4.1.3 順序查找
問題描述：
? 已知有n個元素的數組A[0…n]，給定元素K，要求找出一個下標i,，使得A[i]=K.。輸出第一個值等于K的元素的位置，找不到返回-1。
使用蠻力法解決問題的思路：
? 遍歷數組
算法設計：
Algorithm SequentialSearch(A[0..n-1],K)//輸入：n元數組，給定元素k//輸出：所尋找到的元素k的下標i:=0;while A[i]≠K and i<n do i:=i+1; if A[i]=K then return ielse return -1算法分析：
-
輸入規模
因為輸入的是n元數組，故空間復雜度是：O(n)
-
算法的基本操作
比較A[i]與k是否相同
-
比較次數
- 最壞情況：n
- 最好情況：1
1.4.2 字符串匹配問題
問題描述：
? 從文本中尋找匹配模式的子串，即求出第一個匹配模式的子串在文本中的開始位置（子串最左元素的下標）。
使用蠻力法解決問題的思路：
? 將模式對準文本的前m個字符從左往右進行比對，如果其中有一個字符不匹配，模式往右移動一位繼續下一個m個字符的比對。
算法設計：
Algorithm BFSM (T[0..n-1], P[0..m-1])// Brute Force String Match//輸入：文本數組T[0..n-1]，模式數組P[0..m-1] (n>m)//輸出：所尋找的的位置的下標，查找不成功時返回-1for i :=0 to n-m doj := 0while j<m and P[j]=T[i+j] doj := j+1if j=m return ireturn -1算法分析：
-
輸入規模
輸入了兩個數組，長度分別為n和m，故空間復雜度是：O(n+m)
-
算法的基本操作
比較
-
比較次數
-
最壞情況：
模式需要移動n-m+1次，模塊每次移動前，都要做m次對比，此時的時間復雜度屬于nm級別
-
最好情況：
模式不需要移動，只需要比較m次，時間復雜度屬于m級別
-
平均時間復雜度屬于n級別的
-
1.4.3 最近點對的蠻力算法
問題描述：
? 給定平面S上n個點，找其中的一對點，使得在n(n-1)/2個點對中，該點對的距離最小。
使用蠻力法解決問題的思路：
? 把所有的點兩兩組合，比較它們之間的距離即可以得到距離最小的一對
算法設計：
Algorithm BFCP ( P ) // Brute Force Closest Points// 輸入：n個點的數組P，Pi(xi , yi), i=1, 2, …, n// 輸出：兩個最近點的下標index1和index2dmin := ∞;for i := 1 to n-1 dofor j := i+1 to n dod := sqrt((xi-xj)2+(yi-yj)2);if d < dmin thendmin := d;index1 := i; index2 := j;return index1, index2算法分析：
-
輸入規模
-
算法的基本操作
平方操作
-
比較次數C(n)
C(n)=∑i=1n?1∑j=i+1n2=2∑i=0n?2(n?i)=n(n?1)C(n)={\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}2}=2{\sum_{i=0}^{n-2}(n-i)}=n(n-1) C(n)=i=1∑n?1?j=i+1∑n?2=2i=0∑n?2?(n?i)=n(n?1)
于是C(n)屬于O（n2）
1.4.4 凸包問題的蠻力算法
問題描述：
凸集定義：
? 設S是平面點集，如果S中任意兩點的連線都屬于該集合，則稱S是凸的
凸包定義：
? 一個點集S的凸包是指包含S的最小凸集。顯然，如果S是凸的，則S的凸包就是S本身（橡皮筋圈解釋）。
? 給定一個n個點的點集S，求S的凸包。
使用蠻力法解決問題的思路：
極點：
? 凸集的極點是指不會出現在集合中任何線段的中間的點。
? 設點集大小為n，首先將其中的點兩兩配對，得到直線段條。
? 然后對每一條直線段檢查其余的n-2個點的相對于該直線段的正負性，如果它們都有相同的正負性，那么這條直線段屬于凸多邊形的邊，其頂點是極點。
1.4.5 窮舉法
窮舉法是一種簡單的蠻力方法，它要求生成所有可能的可行解，再從中選擇最優解。
1.4.5.1 NP難問題
目前沒有已知的效率可以用多項式來表示的算法，需要通過窮舉法去解決，下面是兩個經典問題：
1.4.5.2 TSP問題
給定n個城市相互之間的距離，求一條能走遍n個城市的最短路徑，使我們能從任一城市開始，訪問每個城市只一次后回到起點。
1.4.5.3 背包問題
給定n個重量為w1、w2…wn，價值為v1、v2、…、vn的物品和一個承重為W的背包，如何將物品裝入背包使背包所獲的價值最大。
1.4.5.4 分配問題
有n個任務需要分配給n個人執行，一人一個任務。將第j個任務分配給第i個人的成本是C[i, j],求總成本最小的分配方案。
可用窮舉法列出n的階乘個可能的解決方案
總結
以上是生活随笔為你收集整理的算法小结 之 蛮力法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【OpenCV入门教程之十二】OpenC
- 下一篇： 【蓝桥杯每日一练：木头加工】