孫甲霞　陳　俊

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

關(guān)鍵詞:馬鞍點(diǎn);程序設(shè)計(jì);算法;時(shí)間復(fù)雜度;空間復(fù)雜度

中圖分類(lèi)號(hào):TP312 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):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 馬鞍點(diǎn)的定義

若矩陣Am×n的某個(gè)元素ai,j是第i行中的最小值,同時(shí)又是第j列中的最大值,則稱(chēng)此元素為該矩陣中的一個(gè)馬鞍點(diǎn)。

2 依次搜索法

2.1 算法思想

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

2.2 算法

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

{

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) /*判斷這個(gè)(些)最小值是否馬鞍點(diǎn)*/

{

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,判斷每行中的最小值是否為馬鞍點(diǎn),最好情況下每行的最小值只有一個(gè),比較次數(shù)為n-1+m,總共m行,所以最好情況下的比較次數(shù)為m*(n+n-1+m);最壞情況下,每行的元素值都相等,比較次數(shù)為m*n*m。因此,最好情況下,該算法的時(shí)間復(fù)雜度,為O(m*(n+m)),最壞情況下的時(shí)間復(fù)雜度為O(m2*n)。

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

3 多馬鞍點(diǎn)相等法

3.1 馬鞍點(diǎn)的性質(zhì)

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

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

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

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

又因?yàn)锳[x][s]>=A[x][y],可得

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

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

又因?yàn)锳[k][y]<=A[x][y],可得

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

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

2) 和馬鞍點(diǎn)值相等的元素未必是馬鞍點(diǎn),因?yàn)樵撛夭灰欢ㄊ峭兄械淖钚≈?同列中的最大值。

證畢。

3.2 算法思想

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

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

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

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

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

3.3 算法

void Get_Saddle(int A[ ][n],int m,int n)/*找出矩陣中的馬鞍點(diǎ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)/* 若已找到一個(gè)馬鞍點(diǎn) */

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為馬鞍點(diǎn)的值 */

f=1;

saddle=A[i][j];

}

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

}

}

}

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

}

3.4 性能分析

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

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

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

4 小結(jié)

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

參考文獻(xiàn):

[1] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)題集[M].北京:清華大學(xué)出版社,2008:34,195.

[2] 楊路明.C語(yǔ)言程序設(shè)計(jì)[M].2版.北京:北京郵電大學(xué)出版社,2005:107-117.

[3] 譚浩強(qiáng).C程序設(shè)計(jì)題解與上機(jī)指導(dǎo)[M].2版.北京:清華大學(xué)出版社,2000:59-61.

[4] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版[M].北京:清華大學(xué)出版社,1997:13-17.

[5] 周云才.一個(gè)鞍點(diǎn)定理及其應(yīng)用[J].長(zhǎng)江大學(xué)學(xué)報(bào):自然科學(xué)版,2008,5(4):31-32.

[6] 高金泰.鞍點(diǎn)問(wèn)題的一種編程求解方法[J].天水師范學(xué)院學(xué)報(bào),1998(3):44-46.

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

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

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