彭海洋

(河南牧業(yè)經(jīng)濟學院,河南 鄭州 475000)

1 螺旋矩陣的概念與其傳統(tǒng)離線算法

矩陣在計算機中通常用于映射線性空間內(nèi)的運動,特別是對于圖形學方面能夠方便地進行變換等操作。 螺旋矩陣作為矩陣的一種,自身的規(guī)律性可使其作為密鑰等應用于加密或其他算法中[1]。 螺旋矩陣即一個由整數(shù)填充的二維矩陣,從左上角的值為初值,向順時針方向依次遞增,按照“右-下-左-上”的順序依次對矩陣各項賦值,如此循環(huán)直至填充矩陣所有空間。對于空間而言,一般將一個n×n大小的矩陣稱為n階矩陣。 螺旋矩陣的各項值會隨階數(shù)n的不同產(chǎn)生變化,如圖1 所示。

圖1 4 階螺旋矩陣和5 階螺旋矩陣

在實際應用中,螺旋矩陣的階數(shù)具有任意性,通常需要以指定階數(shù)作為參數(shù),由此生成一個特定階數(shù)的矩陣。 目前,構建特定階數(shù)的螺旋矩陣可使用模擬算法:定義矩陣邊長為n,以一個二維數(shù)組matrix[n][n]作為儲存矩陣的數(shù)據(jù)結構。 從matrix[1][1]開始,按照規(guī)律依次將一個遞增的值賦予各項[2]。 如算法1 所示,這種預先將矩陣內(nèi)容存儲在內(nèi)存中的算法,可稱為離線算法。

對于生成螺旋矩陣問題,可利用算法1 將矩陣構建完成后,依次循環(huán)輸出各項值。 由于n階矩陣共有n2項,所以在理想情況下利用此算法,構建時將循環(huán)n2次,輸出時再次循環(huán)n2次。 設算法中所有語句頻度之和為f(n),則有:

對于查詢螺旋矩陣問題,同樣可先行構建完整矩陣。 由于這些算法一般由高級程序設計語言編寫,且作為儲存結構的二維數(shù)組是順序表,各項物理地址相鄰,具有隨機存儲的特性。 因此,無須循環(huán)即可進入所需地址空間并返回相應值。 即在項數(shù)為n2的螺旋矩陣中,查詢某項值的平均查找長度為:

由此可見,在查詢問題中,語句頻度為:

當n充分大時,f1(n) 與f2(n)皆與n2同階,記作T(n)=O(f(n))= O(n2)。 所以此算法在這兩種問題上的時間復雜度同為O(n2)。

僅從時間效率上來看,雖然算法1 的求解速度尚可接受,但在整體上依然存在局限性。 由于在求解中占用的臨時工作單位數(shù)為n2,則在生成與查詢問題中,對每一項都存在n2-1 規(guī)模的空間浪費。 以C++語言為例,通過實驗得知,在VC 環(huán)境下,若以在棧區(qū)分配數(shù)組空間的方式編寫程序,當n大于10 000 時就會因棧內(nèi)存不足導致編譯終止,即無法計算10 000 階及以上階數(shù)的螺旋矩陣。

2 螺旋矩陣在線算法的假設與分析

雖然可以通過在堆區(qū)手動分配內(nèi)存的方式計算更大階數(shù)的螺旋矩陣,但在實際應用中求解較大階數(shù)的螺旋矩陣所需時間與空間的代價或不可接受。 算法1的不足在于借用了龐大的輔助數(shù)組,通過觀察可發(fā)現(xiàn),螺旋矩陣的每一項數(shù)值僅與其矩陣階數(shù)有關。 即當螺旋矩陣的階數(shù)n被確定后,矩陣第i項的值隨之確定,此值記作matrixI。 同時無論階數(shù)n如何變化,矩陣排布規(guī)律依然不變。 所以,可先行假設matrixI與其項數(shù)i對于所在矩陣的階數(shù)n有簡單對照關系,且此對照關系能夠封裝為函數(shù),在程序中通過少量計算求值。 如式(4)所示:

在推導SpiralMatrix 函數(shù)的具體算法之前,可先羅列目前可用的參數(shù)以供輔助研究:(1)當前矩陣項數(shù)i:由用戶查詢時輸入,或在生成時作為循環(huán)參數(shù)依次傳入函數(shù)。 (2)矩陣階數(shù)n:此值由用戶指定,控制當前矩陣大小。

求解螺旋矩陣第i項值時,可將項數(shù)i轉化為坐標xy后計算。 由于矩陣外環(huán)的值可由四角定位,其值也與階數(shù)n有明顯關系,但對于內(nèi)層環(huán)而言,各環(huán)變換皆不相同,難以通過簡單計算求值。 觀察規(guī)律后發(fā)現(xiàn):一個階數(shù)為n的螺旋矩陣,皆能拆為「n/2層循環(huán)遞增的單環(huán),且內(nèi)環(huán)初始值為外環(huán)末值+1。 即矩陣可拆分為多層單環(huán),求解內(nèi)環(huán)時,可將其內(nèi)環(huán)作為階數(shù)是當前環(huán)大小的矩陣外環(huán),求值后再次累加各外環(huán)末值,為方便計算,本文將最外環(huán)定義為0 環(huán)。 具體如圖2 所示。

圖2 螺旋矩陣各項空間關系

于是,對于一種用于生成與查詢螺旋矩陣的在線算法,需要解決以下幾個問題:(1)輸入項數(shù)i,得到對應坐標xy;(2)通過坐標得到當前項所在層數(shù);(3)求解在相應階數(shù)的螺旋矩陣中,保證xy坐標為其外環(huán)時所對應的值;(4)循環(huán)累加各外環(huán)末值;(5)返回最終值。 若以算法方式描述,如算法2 與算法3 所示。

3 螺旋矩陣在線算法的推導

3.1 由項數(shù)i 計算對應坐標

本文為方便理解,設置“1”為初始值,代替計算機常用初值“0”。 在可視為二維數(shù)組的矩陣中,當前項數(shù)值每增大一個階數(shù)值(矩陣邊長),其y坐標就增加1,所以“項數(shù)i/階數(shù)n”的商即為第i項所對應y坐標。同樣,二者相除后所得余數(shù)即為x坐標。

在大多編程語言中可通過“%”運算符直接求得余數(shù),但當被除數(shù)同為階數(shù)時,即當目標項位于矩陣右邊界時,所得商為0。 為了保持算法的統(tǒng)一,盡量將需要判斷的地方以數(shù)學方式計算。 所以在進行除法與求余操作前,可先將項數(shù)i值-1,使“0”暫時作為初值代入計算,最后將結果+1,補回先前扣除值。 計算公式如式(5)與式(6)所示。

3.2 由二維坐標計算當前所在層

明顯看出,階數(shù)為n的螺旋矩陣最大層數(shù)為「n/2,此值記作deep,如式(7)所示。 同時,橫縱坐標皆為deep的項即為所在矩陣的中心點。 所以若要計算當前坐標所在層數(shù),只需計算與中心坐標的距離,再用最大層數(shù)deep減去該值。

這里所求距離基于矩陣空間,與計算物理空間距離不同。 首先計算x坐標與y坐標相對中心線的距離,然后比較兩者大小,其中與中心線較遠的值為當前坐標在矩陣空間下相較其矩陣中心的距離,即當前所在層,或稱當前所在深度,記作curDeep。 本文設定最外層的深度為0,所以在得到curDeep的結果后再次-1。 如式(8)所示。

但是,通過實踐發(fā)現(xiàn),式(7)的求解算法只在奇數(shù)階的矩陣中能夠得到正確值。 對于偶數(shù)矩陣而言,其中心坐標并不對應任何一項。 從空間上看,由螺旋矩陣最后4 項包圍。 所以,式(7)會將本處同一層的4 項計算出不同的深度。 解決方案是拋棄層數(shù)只能為整數(shù)的固有思維,將偶數(shù)階的層數(shù)設定在兩個整數(shù)之間,即為層數(shù)deep額外增加0.5。 同樣,為保持算法統(tǒng)一,可將奇偶數(shù)的判定值取反后作為額外增加值的權重。 改進后的算法如式(9)所示。

3.3 求解坐標為外環(huán)時的數(shù)值

當前xy坐標值是基于n階矩陣所對應的空間位置,若將所處位置視為外環(huán),則必須將“此處深度為0”作為條件求得所符合的新階數(shù),同時計算基于此階數(shù)下對應的坐標。 通過觀察發(fā)現(xiàn),當前深度每增加1,目標階數(shù)隨之減少2。 因為后續(xù)仍需要完整矩陣階數(shù)n,所以新定義當前階數(shù)為curN,并由式(10)賦值。

坐標方面,首先設定矩陣坐標原點在左上角,定義為(1,1)。 則坐標的更新實際上是將坐標原點由(1,1)更改為(curDeep,curDeep)的操作,僅需要通過與上文的當前深度值curDeep相減,即可正確更新坐標。 由于先前坐標不再使用,為節(jié)省空間可直接修改坐標值。 如式(11)所示。

當xy坐標原先就處于外環(huán)時,所減去的深度值為0,保持其值不變。 這就是本文定義最外環(huán)深度為0 的原因。

現(xiàn)在,問題可暫時轉化為:一個寬度為curN的四邊環(huán),各值以順時針反方向遞增,保證xy在其環(huán)上,求對應的值。

對于每一個環(huán),初值總為1,末值可看作從初值累加四次邊長-1 的值,即curN-1,記作last, 由式(12)賦值。

為方便研究,可先在空間上將環(huán)從左上角到右下角分開,使其成為左下部分與右上部分。 對于左下部分各值,可視為以先從Y 軸向下再從X 軸向右的順序依次“遠離”末值。 由于不存在同時在兩個方向上的“移動”,則X 軸與Y 軸分別與末值所在坐標的差值之和,即為與末值空間上的距離,然后用末值減去這個距離,得到處于左下部分的項的值。 定義為valueI_left。由末值坐標(1,2),得出式(13)。

同理,對于右上部分各值,可視為依次“遠離”初值,且距離越遠數(shù)值越大,該值定義為valueI_right。 由末值坐標(1,2),得出式(14)。

可見,當坐標y值大于x值時,此項位于左下部分,反之處于右上部分。 可利用三目運算符,將式(13)與式(14)合成式(15),并把值合并定義為valueI。

至此,已獲得可構建出矩陣的所有數(shù)據(jù),不妨先行驗證一次。 本文使用for 循環(huán)語句,定義整型變量I,循環(huán)自增至n2,以I為參數(shù),求出對應值后輸出,同時每輸出n個值后換行。 設置n值為12,構建12 階矩陣作為示例,如圖3 所示。 輸出符合預期,只需再求出各外環(huán)末值之和,便可構建正確的螺旋矩陣。

圖3 螺旋旋矩拆解為各單環(huán)

3.4 求解各外環(huán)末值之和

由式(12)可計算出某一階外環(huán)的末值。 對于求解各外環(huán)末值之和問題,可從當前矩陣最外環(huán),即深度為0 的環(huán)開始,到當前深度環(huán)為止,循環(huán)使用式(12)求出對應環(huán)末值并累加。 本文研究在線算法的目的之一,是要規(guī)避算法中出現(xiàn)的循環(huán)結構。 為得到簡潔的公式,先由循環(huán)思想出發(fā),定義deepI為循環(huán)計算中累計求值所使用的當前階數(shù),循環(huán)語句為式(16)。

定義各外環(huán)末值之和為acc,在循環(huán)語句中累加,如式(17)所示。

通過通項公式簡單計算,可得到式(19),這是一個不包含deepI的公式,計算結果為各外環(huán)末值之和。 最后將式(15)中的valueI與acc相加,即可直接計算得到當前項在螺旋矩陣中的值。

最后,同樣以12 階為例,順序計算后輸出,檢驗算法準確度,如圖4 所示。

圖4 12 階的螺旋矩陣

可以看到,在生成螺旋矩陣方面,本文研究的算法可準確計算矩陣各項值,所以本算法也可應用在查詢螺旋矩陣問題上。

4 螺旋矩陣在線算法與傳統(tǒng)離線算法在性能上的對比

在生成螺旋矩陣問題中,由于不可避免地需要遍歷一次大小為n2的矩陣,則本算法的時間復雜度與算法1 的時間復雜度相同,為O(n2)。 而在空間上,本算法省去了預先構建矩陣的操作,無需使用輔助數(shù)組,空間復雜度為S(1),小于算法1 的空間復雜度S(n2),性能上整體優(yōu)于算法1。 在查詢螺旋矩陣問題中,同樣因為無需提前計算矩陣各值,所以本算法的時間復雜度降至O(1),空間復雜度同樣降至S(1)。 在性能上全面優(yōu)于算法1。

如圖5、圖6、圖7 和圖8 所示,展示了傳統(tǒng)離線算法與在線算法在求解這兩種問題時分別在時間與空間上的差異。 其中編譯與運行環(huán)境為VC,所有變量在棧區(qū)定義,查詢項為項數(shù)中間值n2/2,記錄時間不包括輸入與輸出所占的時間。 所有結果為多次實驗取平均值。

圖5 生成操作的時間對比

圖6 生成操作的內(nèi)存空間對比

圖7 查詢操作的時間對比

圖8 查詢操作的內(nèi)存空間對比

從圖表可直觀看出,除了在生成操作上在線算法較常規(guī)算法有系數(shù)級別的額外時間損耗外,對于其余3種操作,在線算法在效率上都遠遠優(yōu)于常規(guī)算法,特別是在線算法也可計算常規(guī)算法無法求解的大階數(shù)螺旋矩陣。