求解馬鞍點的兩種算法及性能分析

孫甲霞　陳　俊

摘要:求解矩陣中的馬鞍點是計算機程序設計中的常見問題。結合矩陣中馬鞍點的特點,給出了求解矩陣中的馬鞍點的依次搜索法和多馬鞍點相等法,詳細敘述了它們的算法思想,特別對多馬鞍點相等法的理論基礎做了證明,分別給出了對應的算法。最后針對這兩種算法進行了時間性能和空間性能的分析和比較,總結了兩種算法各自的優(yōu)缺點。

關鍵詞:馬鞍點;程序設計;算法;時間復雜度;空間復雜度

中圖分類號:TP312 文獻標識碼:A 文章編號:1009-3044(2009)15-4063-03

Two Algorithms about Solving the Saddle Point and Analyzing Performance

SUN Jia-xia, CHEN Jun

(The School of Information Technology, Henan Institute of Science and Technology, Xinxiang 453003, China)

Abstract: To solve the saddle point is the common problem in computer programming. Combine with the characteristic of saddle point in matrix, the paper propose two algorithms to solve the saddle point , such as the method of search in turnand the equal of multi saddle point. And describe the thinking and corresponding code of the algorithm in detail, especially, the method of equal of multi saddle point is proved. Last the time and space performance of the arithmetic are analyzed and compared, and summarize the respective advantage and disadvantage of the two algorithms.

Key words: saddle point; programming; algorithm; time complexity; space complexity

1 馬鞍點的定義

若矩陣Am×n的某個元素ai,j是第i行中的最小值,同時又是第j列中的最大值,則稱此元素為該矩陣中的一個馬鞍點。

2 依次搜索法

2.1 算法思想

對于矩陣的每一行,掃描第一遍求出該行的最小元素值;掃描第二遍,對于和最小元素值相等的每個元素(可能是馬鞍點),掃描其所在列,若是該列的最大元素值,則為馬鞍點,輸出該元素的信息。

2.2 算法

void Get_Saddle(int A[m][n]) /*求矩陣A中的馬鞍點*/

{

for(i=0;i

{

for(min=A[i][0],j=0;j

if(A[i][j]

for(j=0;j

if(A[i][j]==min) /*判斷這個(些)最小值是否馬鞍點*/

{

for(flag=1,k=0;k

if(min

if(flag)

printf("Found a saddle element! A[%d][%d]=%d",i,j,A[i][j]);

}

}//for

}//Get_Saddle

2.3 性能分析

該算法的基本操為元素的比較,求每行的最小元素值比較次數(shù)為n,判斷每行中的最小值是否為馬鞍點,最好情況下每行的最小值只有一個,比較次數(shù)為n-1+m,總共m行,所以最好情況下的比較次數(shù)為m*(n+n-1+m);最壞情況下,每行的元素值都相等,比較次數(shù)為m*n*m。因此,最好情況下,該算法的時間復雜度,為O(m*(n+m)),最壞情況下的時間復雜度為O(m2*n)。

該算法的空間復雜度為O(0)。

3 多馬鞍點相等法

3.1 馬鞍點的性質(zhì)

若在一個矩陣中存在多個馬鞍點,則這些馬鞍點的值必相同;反之,和馬鞍點值相等的元素,不一定是馬鞍點。以下為證明。

證明:1) 設矩陣A[m][n]中存在馬鞍點,馬鞍點為A[x][y]。根據(jù)馬鞍點的定義,該元素是其所在行的最小值,是其所在列的最大值,可知對于任一元素A[x][j](j!=y),必有A[x][j]>=A[x][y];對于任一元素A[i][y](i!=x),必有A[i][y]<=A[x][y]。

若矩陣中存在另一馬鞍點A[k][s](k!=x且s!=y),則:

A[k][s]>= A[x][s](A[k][s]為第s列中的最大值)

又因為A[x][s]>=A[x][y],可得

A[k][s]>= A[x][y] (式1);

A[k][s]<= A[k][y](A[k][s]為第k行中的最小值)

又因為A[k][y]<=A[x][y],可得

A[k][s]<= A[x][y] (式2);

式1和式2聯(lián)立可得:A[k][s] = A[x][y]。

2) 和馬鞍點值相等的元素未必是馬鞍點,因為該元素不一定是同行中的最小值,同列中的最大值。

證畢。

3.2 算法思想

根據(jù)馬鞍點的定義,馬鞍點一定等于其所在行的最小值,因此,只需判斷和每行最小值相等的元素是否為馬鞍點即可;根據(jù)上述性質(zhì),若已找到一個馬鞍點saddle,則其他馬鞍點的值一定等于saddle,此時先比較一行中的最小值是否等于saddle,若不等,則該行不存在馬鞍點;若相等,需進一步判斷和該行最小值相等的元素是否是其所在行的最大值。

設兩個輔助數(shù)組min[]和max[],分別用來存放每行的最小元素值和每列的最大元素值;設變量saddle用來存放馬鞍點的值,變量f用來表示是否已找到一個馬鞍點。

首先掃描矩陣,求出每行的最小值,存入min數(shù)組中相應的單元;

第二次掃描矩陣,求出每列的最大值,存入max數(shù)組中的相應單元;

第三次掃描矩陣,找出所有的馬鞍點。對于第i行,若f=1,即已找到一個馬鞍點,只需將min[i]和馬鞍點的值saddle進行比較,若不相等,則該行不存在馬鞍點,繼續(xù)掃描下一行;若相等,需進一步判斷和min[i]相等的元素是否等于其所在列的最大值,若是,則為馬鞍點,否則不是。若f=0,即還未找到馬鞍點,須判斷和min[i]相等的所有元素是否等于其所在列的最大值,若是,則為馬鞍點,令f=1,saddle為馬鞍點的值,否則不是。

3.3 算法

void Get_Saddle(int A[ ][n],int m,int n)/*找出矩陣中的馬鞍點*/

{

f=0;

for(i=0;i

{

min[i]=A[i][0];

for(j=1;j

if(A[i][j]

}

for(j=0;j

{

max[j]=A[0][j];

for(i=1;i

if(A[i][j]>max[j]) max[j]=A[i][j];

}

for(i=0;i

{

if(f==1)/* 若已找到一個馬鞍點 */

if(min[i]!=saddle) continue;/*若該行的最小元素值不等于saddle,查找下一行*/

for(j=0;j

{

if(A[i][j]==min[i])/* A[i][j]等于該行最小值 */

if(A[i][j]==max[j]) /* A[i][j]等于該列最大值*/

{

if(f==0)

{/* 置f為1,saddle為馬鞍點的值 */

f=1;

saddle=A[i][j];

}

printf("found a saddle A[%d][%d]=%d ",i,j,A[i][j]);/* 輸出馬鞍點 */

}

}

}

if(f==0) printf("there is not saddle.");/* 若不存在馬鞍點,輸出不存在的信息 */

}

3.4 性能分析

該算法的基本操作仍然是元素的比較。第一遍掃描矩陣求每行最小值的比較次數(shù)是m*n;第二次掃描矩陣求每列最大值的比較次數(shù)是m*n;第三次掃描矩陣找馬鞍點的比較次數(shù):無馬鞍點的情況下,比較次數(shù)為m*n,存在馬鞍點的情況下,最好情況下(只有一個馬鞍點且存在第一行),比較次數(shù)為n+m-1;最壞情況下(矩陣中的元素都是馬鞍點),比較次數(shù)為m*2n;

因此,該算法在最壞情況下的比較次數(shù)為m*n+m*n+m*2n=4m*n,時間復雜度為O(m*n)。

該算法用了兩個數(shù)組作為輔助空間,大小分別是m和n,因此空間復雜度是O(m+n)。

4 小結

求解矩陣中的馬鞍點的方法有多種,這里只列出兩種?？梢钥闯龅谝环N方法的算法思想比較簡單,所用的輔助空間較小,但時間效率較差;第二種方法的算法思想相對較復雜,利用了“矩陣中的馬鞍點值均相等”的性質(zhì),時間效率好于第一種方法,特別是在矩陣較大的情況下,但所占用的空間要大一些。

參考文獻:

[1] 嚴蔚敏.數(shù)據(jù)結構題集[M].北京:清華大學出版社,2008:34,195.

[2] 楊路明.C語言程序設計[M].2版.北京:北京郵電大學出版社,2005:107-117.

[3] 譚浩強.C程序設計題解與上機指導[M].2版.北京:清華大學出版社,2000:59-61.

[4] 嚴蔚敏.數(shù)據(jù)結構C語言版[M].北京:清華大學出版社,1997:13-17.

[5] 周云才.一個鞍點定理及其應用[J].長江大學學報:自然科學版,2008,5(4):31-32.

[6] 高金泰.鞍點問題的一種編程求解方法[J].天水師范學院學報,1998(3):44-46.

[7] 劉軍.淺析算法設計與算法時間復雜度[J].電腦知識與技術,2008(14):878-879.

[8] 楊朝霞.分析和計算算法效率的便捷方法[J].蘭州交通大學學報,2004(4):78-82.

[9] 網(wǎng)絡技術[EB/OL].http://www.cnfan.net.