Q-matrix

Q-matrix

Q-matrix這個詞是從Markov process來的,為transition rate matrix的簡稱:http://en.wikipedia.org/wiki/Continuous-time_Markov_process

在程式設計中,Q-matrix則是意指一種特別的手法:把recurrence formula化作transition rate matrix(即Q-matrix)──計算數列第N項的值時,從原本的遞迴計算,轉變成矩陣次方計算。至於矩陣次方計算可以利用Divide and Conquer解決,請見「Divide and Conquer──Fast Exponentiation」一文。

舉個實例。現在要計算Fibonacci數列的第N項。

這個手法的好處,在於計算第N項時,原本用遞迴式一項一項計算,需要O(N)時間;現在改用矩陣次方計算,只需要O(lgN)時間。

recurrence的計算歸納如下:一、運用Dynamic Programming:算出每一項的值,並存在表格中,需要O(N)時間。二、Q-matrix:只能算出某一項的值,需要O(lgN)時間。

本文所介紹的手法,目前並未有正式稱呼,只是大家習慣稱此手法為Q-matrix。在數學家眼中,Q-matrix與剛才程式碼當中的矩陣是不一樣的:http://mathworld.wolfram.com/FibonacciQ-Matrix.html

綜觀此手法,其實就是轉換數域、改變計算方法, 運用改變後的特性,進而讓電腦程式更快速的求得答案。

轉換數域以配合電腦程式做計算, 例如影像處理常用的Hough transform就是一例。

recurrence和transition rate matrix本質上是同一種東西。 他們其實都在描述數列當中前後項之間的關係,只是以不同型態呈現而已。轉換數域,其實也就是將資料以不同型態呈現罷了。

每當遇到一個難纏的問題時,不妨換換思考角度,將資料以不同面向來看待,或許能找到不錯的新方法。

UVa 10518 10655 10743 10754 10870