634521逆序數(shù)怎么求

634521逆序數(shù)是12。逆序數(shù)含義：在n個(gè)數(shù)碼1，2，…，n的全排列j1j2…jn中，若一個(gè)較大的數(shù)碼排在一個(gè)較小的數(shù)碼的前面，則稱它們構(gòu)成反序，亦稱逆序。求逆序數(shù)時(shí)，可以從前到后將相鄰的兩個(gè)數(shù)進(jìn)行比較，求出逆序及逆序數(shù)。

逆序數(shù)的計(jì)算

直接計(jì)數(shù)

計(jì)算一個(gè)排列的逆序數(shù)的直接方法是逐個(gè)枚舉逆序，同時(shí)統(tǒng)計(jì)個(gè)數(shù)。例如在序列{2,4,3,1}中，逆序依次為(2,1)，(4,3)，(4,1)，(3,1)，因此該序列的逆序數(shù)為4。

歸并排序

直接計(jì)數(shù)法雖然簡(jiǎn)單直觀，但是其時(shí)間復(fù)雜度是O(n^2)。一個(gè)更快（但稍復(fù)雜）的計(jì)算方法是在歸并排序的同時(shí)計(jì)算逆序數(shù)。