逆序數怎麼算?

怎樣求逆序數

這個的是0

1後面<1的數0個＋2後面<2的數0個＋3後面<3的數0個＝0

可以推廣為（a,b,c,……，z)

a後面小於a的數A個……一直加到z後面小於z的數Z個

即為它的逆序數！

排列，1，6，5，3，4，2的逆序數是多少，怎麼樣算，急

逆序數是逆序的個數，”逆序”是相對“

”順序”而言的。“順序”是指由小到大的自然數順序，如：1，2，3……所以，這道題的逆序對為6，5；6，3；6，4；6，2；5，3；5，4；5，2；3，2；4，2。所以逆序數為9。

逆序數怎麼求

我收集到的有兩種方法：歸併排序和樹狀數組。

1、歸併排序：

假設a[l...r]這個數組，先二分mid=(l+r)/2；那麼我們假設已經求出了a[l...mid],a[mid+1...r]這兩段元素的逆序數且排好序，於是可以將這兩段歸併了，歸併的同時計算逆序數，如果前段的數小於後段的數，屬於正常排序，反之，就會有逆序數產生。假設l<=i<=mid,mid+1<=j<=r,如果有a[i]>a[j]，這樣的發生說明在a的前段中i...mid的元素都比a[j]大，於是逆序數+=mid-i；如果a[i]

2、樹狀數組：

我們先假設一個1...n自然數排列，n不是很大，於是這樣就可以申請一個n個空間的a數組，首先全部置0，每次將排列中的數i取出（從左到右取出），改變a數組的元素的值為1（1），然後求出a[1...i-1],的和（1），這個和就是小於i的值的和sum，就是i這個數的逆序數。這裡的（1）、（2）就會用到樹狀數組的logn時間複雜度的算法。

但是這裡說自然數的範圍很大比如（0-999，999，999）時候，而個數不多時。這樣是情況才是作者想考察我們算法的東西，那麼這裡就要說說離散化的用法了。

離散化：其實我開始理解就是想的很多大數據用數組來存儲，那麼下標就代表了數據本身了，舉個簡單的列子。

1、1000、100000、100000、999。

這樣一串數，如果用數組來存儲，只需要開闢5個int空間就夠了。這樣就把離散的大數據很輕巧的裝到小盒子裡面了。這樣說，其實你可能還在懵懂中，因為這樣的方法好像隨處可見，我開始也是這樣想的，沒什麼特別的，但是當我看到了一個別人博客裡做的離散化題目後才深切的體會。那麼下面讓我們來看看在逆序數中的用法吧！

如果將逆序數的本質找到就可以很好理解了，求逆序數其實就求每個數的逆序數之和，如果要求當前逆序數，則是找當前數的後續數中比他小的數的個數，然後在抽象一下就可以知道，其實對於逆序數而言，與元素的本身沒關係，而是與元素與元素之間的大小有關係，這點理解到的很重要的。

既然是元素與元素之間大小相關的話，我們就可以這樣看的問題了，對於上面的一串數可以用另外一串具有最小數據本身的數來替代，假設用3、40、50、60、20，比較一下，可以看出他們元素與元素之間的大小關係是一樣的。於是我們就可以進一步推測能夠找到最小串的自然數來替代了，就是1、3、4、5、2。看看吧！這串數夠小了吧，而且關係和上面的大數據也相同，即是說逆序數相同。

如果找到了這樣的一串數來替代大數據的話，我們就可以開小空間數組來存儲這些數了。然後就可以用樹狀數組來求出逆序數，複雜度為nlogn。

這裡就要想怎樣求得這樣的串了，其實稍微一想便知道，其實這串數就是大數據的排名情況。比如1000排名第3，於是1000就是3。求排名其實就是求一個排序，排序後的數組下標就是該數據的排名。於是我們會問，你怎麼知道該數據和下標的對應關係呢？

假設我們為每個大數據建立起1對1的關係的話就好說了。

struct Ln

{

int a;//表示大數據

int b;//表示下標ln[i],這裡的i==b

}

Ln ln[N];

建立好對應關係後，對ln排序，排好序後每個小標都有排名了，即是大數據的排名，然後將他放入a數組中，建立......

行列式逆序數怎麼算

按第一列展開,D11=1,D12=3,D13=2,正負號就看他們的下標和是負數還是正數,如：D11的下標和是2,D13的下標和是4,所以是正的

行列式的逆序數怎麼算

只計算行逆序數（列號升序的情況下）或者列逆序數（行號已經按升序排列的情況下）

求3756412的逆序數？

在3後面比它小的有2個，逆序數為2

在7後面比它小的有5個，逆序數為5

在5後面比它小的有3個，逆序數為3

在6後面比它小的有3個，逆序數為3

在4後面比它小的有2個，逆序數為2

在1後面比它小的有0個，逆序數為0

所以序列的逆序數有2+5+3+3+2=15

逆序數的逆序數的計算

計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。例如在序列 { 2, 4, 3, 1 } 中，逆序依次為 (2,1), (4,3), (4,1), (3,1)，因此該序列的逆序數為 4。下面這個 Visual Basic 6.0 編寫的示例使用的就是直接計數的方法，函數 NiXushu 返回一個字符串的逆序數。Private Function NiXuShu(ByVal l As String) As Long '逆序數計算Dim i As Integer, j As Integer, c As LongDim n() As IntegerReDim n(Len(l))For i = 1 To Len(l)n(i) = Val(Mid(l, i, 1))For j = 1 To i - 1If n(i) < n(j) Thenc = c + 1End IfNext jNext iNiXuShu = cEnd Function 直接計數法雖然簡單直觀，但是其時間複雜度是 O(n^2)。一個更快（但稍複雜）的計算方法是在歸併排序的同時計算逆序數。下面這個 C++ 編寫的例子演示了計算方法。函數 mergeSort() 返回序列的逆序數。int is1[n],is2[n];// is1為原數組，is2為臨時數組，n為個人定義的長度long mergeSort(int a,int b)// 下標，例如數組int is[5]，全部排序的調用為mergeSort(0,4){if(a