計算反演次數（概念上？）

Question

所有的，我想知道我們究竟是如何計算兩個數組之間的反轉次數的。

比方說，例如，我們有以下兩個數組：

A = [1，2，3，4，5，6] B = [6,3,1，5,4，2， 1]

我如何計算概念上的反演次數？也就是說，只要看看這兩個陣列，不考慮涉及的編碼。另外，我知道兩個數組之間繪製線段的約定，但我試圖在這裏獲得更深入的理解。

謝謝！

Answer 1

我不確定兩個數組的反轉數是什麼意思。

對於一個陣列： 反演是一對（a，b），其中a在b之前的順序爲a> b。因此，從概念上講，你可以嘗試每一對B。讓我們從6開始，有5個反轉：（6,3），（6,5），（6,4），（6,2），（6， 1）。接下來是3，只有2：（3,2），（3,1）。等等，這裏的結果是13.

但是，這個算法是非常天真的，運行O（n^2）。更好的解決方案是基於合併排序算法，並以O（n log n）運行。你可以檢查它here。我認爲這隻適用於已經排序的第一個數組。

對於兩個陣列：當涉及到2門陣列（再次在概念上），只要輸入你的乙陣列上方A排列並繪製連接相同的元件線。交叉點的數量應該是反轉次數。這正是上面鏈接的基於合併分類的算法的工作原理。看看下面的圖片：

的結果仍是13，所以這種方法確實有效。