申論題

一、考慮數字1到n，若將其順序重新排置，每個排列順序都稱作一個排列或置換 （Permutation），例如5 1 4 3 2是1 2 3 4 5的一個排列。我們可以將一個數字1 到n的排列視為一個順序的映射P，則前述例子可表示為P(5) = 1、P(1) = 2、 P(4) = 3、P(3) = 4、P(2) = 5。當然，1 2 3 4 5也是1 2 3 4 5的一個排列。在 一個數字1到n的排列P中，若一對數字 i和 j，1 ≦ i ＜ j ≦ n，P(j) ＜ P(i)，也就是在排列P中較大的數字 j出現在較小的數字 i左邊（前面），我們稱此 對數字為反向（Inversion），而排列P的反向數（Inversion number）則定義 為排列P中反向的總數量。請回答下列問題：

(二)若給定一個數字1到n的排列P，請提出一個線性遞迴（Linear Recursive） 的方式來算出排列P的反向數，並提供虛擬碼（Pseudo-code）與時間複 雜度分析。