Function

Function

「函數」這個翻譯非常不直覺。函數其實是「對應」與「變換」兩種概念的結合。

對應,就是一個東西對應一個東西。變換,就是從一個東西,按照對應關係,變成另一個東西。

函數的規定

輸入都是同一類的東西。輸出都是同一類的東西。輸入與輸出可以同類、也可以不同類。輸入數量和輸出數量沒有任何限制。

相異輸入可以對應到相同輸出,但是相同輸入不可以對應到相異輸出。

必須用到每個輸入,但是不一定要用到每個輸出。被用到的輸出們,稱作「像image」。

顯然,用到的輸入數量大於等於用到的輸出數量。

這些刁鑽古怪的規定,讓函數獨樹一格。宛如中醫利用藥的偏性來治病,數學家利用函數的特性來解題。

反函數(inverse)

一個函數的「反函數」,就是對調輸入輸出、反轉對應方向所形成的函數。反函數必須符合函數的規定。原本函數要擁有反函數的話,就必須用到每個輸出、相同輸出不可以對應到相異輸入──也就是說,輸入數量與輸出數量必須相等,而且恰好一一對應。

顯然,當f的反函數是g,則g的反函數是f。

想要表達反過來對應這件事,竟然還得符合函數的規定,實在很莫名其妙。直接發明一個「反對應」的概念不就好了?當然可以呀!只是數學家鮮少討論這件事而已。

函數的用法

函數可以描述兩件事物的關聯。例如三角函數就是三角形內角與邊長的關聯。半徑與圓周長、整數和質因數分解,通通可以寫成函數。

令x代表一個圓的半徑
perimeter(x) = 2πx

函數可以描述一件事物具有附屬屬性。例如一個人具有身高、具有體重。概念類似於中文的「的」、英文的「of」。

令x代表一個人
height(x)  一個人的身高
weight(x)  一個人的體重

函數可以描述從事一件事情的結果。

令x代表移動的方向,令f(x)代表移動的距離
f(east) = (+1,0)  往東,則x座標多一
f(west) = (-1,0)  往西,則x座標少一

函數可以描述圖形。函數的輸入和輸出必須是數值,當作是座標。例如愛心方程式。

函數還有各式各樣的用法,族繁不及備載。

Cycle Finding

Self-mapped Function in a Finite Set

此處我們討論電腦運算經常遭遇的一種函數:輸入與輸出完全相同、數量有限個(離散可數)的函數。

簡單的解讀方式:一群點,每一點只有一條出路,通往別人、亦得通往自己。

這種函數有著非常重要的特性:從任何一點出發,不斷往前走,最後必定繞圈、循環!

Cycle Finding

給定出發起點,請找到循環起點、循環長度。

應用廣泛,儘管外表看不出端倪。考驗你看穿事情本質的能力。

一、檢查一條list是否接錯而造成無限循環,並且找出接錯位置。
二、檢查兩條獨立的list是否接錯而牽連作伙,並且找出接錯位置。
三、一條陣列緊密放著n+1個數,數值皆介於1到n,
  其中恰有兩數相同,請找出此數及此數位置。
四、整數除法,商數的循環節。
五、餘數次方,次方值的模數。
六、檢查自動機是否有無窮迴圈。

Cycle Finding: Memoization

演算法(Memoization)

建立一條陣列,記錄各個元素是否拜訪過了。當遇到拜訪過的元素,就是循環起點。

這個方法既簡單又快,不過缺點就是記憶體用很兇。時間複雜度為O(N),空間複雜度為O(N),N為集合大小。

UVa 202 275 517 11549 12442 11607

Cycle Finding: Floyd's Algorithm(Tortoise and Hare Algorithm)

龜兔賽跑演算法

以龜兔兩個變數就能找到循環,相當節省記憶體。

一、尋找循環長度的倍數:

龜兔從起點同時出發,龜走一步、兔就走兩步。由於兔比龜快,當龜兔皆進入循環之中,兔必然領先數圈、從後方追上龜。

當龜兔相遇,龜兔的行走距離差,即是循環長度的倍數。龜一倍速、兔兩倍速,龜兔的行走距離差,剛好是龜的行進距離。龜的行進距離即是循環長度的倍數。

二、尋找循環起點:

龜退回起點,兔原地待命,龜兔同時出發,龜走一步、兔走一步。龜兔相遇之處即是循環起點。

三、尋找循環長度:

從循環之中任意一處出發,一次走一步,繞一圈回到原處,即得循環長度。

時間複雜度

最佳情況是:當龜進入循環,正好龜兔相遇。

最差情況是:當龜進入循環,此時兔恰好在龜前方一步之距,兔得再繞兩圈才能追上龜。

令μ是出發起點到循環起點的距離,λ是循環長度。龜最多走μ + λ步,兔最多走2μ + 2λ步,時間複雜度為3μ + 3λ = O(μ + λ)。

UVa 350 11053

Cycle Finding: Brent's Algorithm

演算法

一、尋找循環長度:

龜兔位於起點,龜保持不動,兔一步一步走。如果龜位於循環之中,那麼兔便可從後方追上龜,測量出循環長度。概念跟Floyd's Algorithm完全相同。

因為不知道龜是否位於循環之中,龜必須不時移動到兔的當前位置,讓龜有機會進入循環之中、讓兔有機會從後方追上龜。此處採用倍增法,每當兔走1步、續走2步、續走4步、……,龜會瞬間出現在兔的當前位置。

最差情況是出發起點與循環起點相距很遠,龜在進入循環前一刻,兔將多繞許多圈。然而多繞的步數其實小於等於μ(以倍增法推導),又由於龜不必移動,因而效率較佳。

二、尋找循環起點:

龜兔退回出發點。兔先走循環長度步,之後就跟Floyd's Algorithm完全相同。

由於兔額外移動,因而效率較差。