什麼是逆序對？
* 如有一個陣列A[4,5]，索引0<1，且A[0]<A[1]，此為非逆序對。
* 如有一個陣列A[5,4]，索引0<1，且A[0]>A[1]，此為逆序對。
* 用以衡量數列的有序程度，逆序對越多，數列越無序。
舉例
有一數列[3, 1, 2, 4]，求有幾對逆序對？
（0,1）,3>1，是一逆序對。
（0,2）,3>2，是一逆序對。
（0,3）,3<4，不是一逆序對。
（1,2）,1<2，不是一逆序對。
（1,3）,1<4，不是一逆序對。
（2,3）,2<4，不是一逆序對。
共有兩對逆序對（0,1）、（0,2）。
Python 實現
暴力求解，時間複雜度為執行次數隨資料量大小的趨勢，資料量n兩個巢狀迴圈使資料量變成n^2，即執行次數，所以時間複雜度為O(n^2)。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def count_inversion(a): | |
| count=0 | |
| for i in range(len(a)): | |
| for j in range(i+1,len(a)): | |
| if a[i]>a[j]: | |
| count+=1 | |
| return count | |
| print(count_inversion([3, 1, 2, 4])) | |
| #output:2 |
沒有留言:
張貼留言
寫下幸福點子吧！