Дан массив, найдите общее количество его инверсий. Если (i < j) а также (A[i] > A[j]), затем пара (i, j) называется инверсией массива A. Нам нужно посчитать все такие пары в массиве.
Например,
Input: A[] = [1, 9, 6, 4, 5]
Output: The inversion count is 5
There are 5 inversions in the array: (9, 6), (9, 4), (9, 5), (6, 4), (6, 5)
Потренируйтесь в этой проблеме
1. Решение грубой силы
Простым решением было бы для каждого элемента массива подсчитать все элементы, меньшие его справа, и добавить счетчик к выводу. Сложность этого решения O(n2), куда n это размер ввода.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <stdio.h> // Функция для определения количества инверсий заданного массива int findInversionCount(int arr[], int n) { int inversionCount = 0; for (int i = 0; i < n — 1; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] > arr[j]) { inversionCount++; } } } return inversionCount; } int main() { int arr[] = { 1, 9, 6, 4, 5 }; int N = sizeof(arr)/sizeof(arr[0]); printf(«The inversion count is %d», findInversionCount(arr, N)); return 0; } |
Скачать Выполнить код
результат:
The inversion count is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Main { // Функция для определения количества инверсий заданного массива public static int findInversionCount(int[] arr) { int inversionCount = 0; for (int i = 0; i < arr.length — 1; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] > arr[j]) { inversionCount++; } } } return inversionCount; } public static void main(String[] args) { int[] arr = { 1, 9, 6, 4, 5 }; System.out.println(«The inversion count is « + findInversionCount(arr)); } } |
Скачать Выполнить код
результат:
The inversion count is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Функция для определения количества инверсий заданного списка def findInversionCount(A): inversionCount = 0 for i in range(len(A) — 1): for j in range(i + 1, len(A)): if A[i] > A[j]: inversionCount = inversionCount + 1 return inversionCount if __name__ == ‘__main__’: A = [1, 9, 6, 4, 5] print(«Inversion count is», findInversionCount(A)) |
Скачать Выполнить код
результат:
The inversion count is 5
2. Использование сортировки слиянием
Это классическая проблема, которую можно решить алгоритм сортировки слиянием. По сути, для каждого элемента массива подсчитайте все элементы, находящиеся слева от него, и добавьте счет к выходным данным. Вся эта магия происходит внутри функции слияния сортировки слиянием.
Рассмотрим два подмассива, участвующих в процессе слияния:
Реализацию можно увидеть ниже на C, Java и Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <stdio.h> // Объединяем два отсортированных подмассива `arr[low…mid]` и `arr[mid+1…high]` int Merge(int arr[], int aux[], int low, int mid, int high) { int k = low, i = low, j = mid + 1; int inversionCount = 0; // пока есть элементы в левом и правом рядах while (i <= mid && j <= high) { if (arr[i] <= arr[j]) { aux[k++] = arr[i++]; } else { aux[k++] = arr[j++]; inversionCount += (mid — i + 1); // ПРИМЕЧАНИЕ } } // копируем оставшиеся элементы while (i <= mid) { aux[k++] = arr[i++]; } /* не нужно копировать вторую половину (поскольку остальные элементы уже находятся в правильном месте во временном массиве) */ // копируем обратно в исходный массив, чтобы отразить порядок сортировки for (int i = low; i <= high; i++) { arr[i] = aux[i]; } return inversionCount; } // Сортируем массив `arr[low…high]`, используя вспомогательный массив `aux` int MergeSort(int arr[], int aux[], int low, int high) { // базовый вариант if (high <= low) { // если размер прогона <= 1 return 0; } // найти середину int mid = (low + ((high — low) >> 1)); int inversionCount = 0; // рекурсивно разделяем прогоны на две половины до тех пор, пока размер прогона не станет <= 1, // затем объединяет их и возвращает вверх по цепочке вызовов // разделить/объединить левую половину inversionCount += MergeSort(arr, aux, low, mid); // разделить/объединить правую половину inversionCount += MergeSort(arr, aux, mid + 1, high); // объединяем две половинки inversionCount += Merge(arr, aux, low, mid, high); return inversionCount; } int main() { int arr[] = { 1, 9, 6, 4, 5 }; int N = sizeof(arr)/sizeof(arr[0]); int aux[N]; for (int i = 0; i < N; i++) { aux[i] = arr[i]; } // получить количество инверсий, выполнив сортировку слиянием на arr printf(«The inversion count is %d», MergeSort(arr, aux, 0, N — 1)); return 0; } |
Скачать Выполнить код
результат:
The inversion count is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
import java.util.Arrays; class Main { // Объединяем два отсортированных подмассива `arr[low…mid]` и `arr[mid+1…high]` public static int merge(int[] arr, int[] aux, int low, int mid, int high) { int k = low, i = low, j = mid + 1; int inversionCount = 0; // пока есть элементы в левом и правом рядах while (i <= mid && j <= high) { if (arr[i] <= arr[j]) { aux[k++] = arr[i++]; } else { aux[k++] = arr[j++]; inversionCount += (mid — i + 1); // ПРИМЕЧАНИЕ } } // копируем оставшиеся элементы while (i <= mid) { aux[k++] = arr[i++]; } /* не нужно копировать вторую половину (поскольку остальные элементы уже находятся в правильном месте во временном массиве) */ // копируем обратно в исходный массив, чтобы отразить порядок сортировки for (i = low; i <= high; i++) { arr[i] = aux[i]; } return inversionCount; } // Сортируем массив `arr[low…high]`, используя вспомогательный массив `aux` public static int mergesort(int[] arr, int[] aux, int low, int high) { // базовый вариант if (high <= low) { // если размер прогона <= 1 return 0; } // найти середину int mid = (low + ((high — low) >> 1)); int inversionCount = 0; // рекурсивно разделяем прогоны на две половины до тех пор, пока размер прогона не станет <= 1, // затем объединяет их и возвращает вверх по цепочке вызовов // разделить/объединить левую половину inversionCount += mergesort(arr, aux, low, mid); // разделить/объединить правую половину inversionCount += mergesort(arr, aux, mid + 1, high); // объединяем две половинки inversionCount += merge(arr, aux, low, mid, high); return inversionCount; } public static void main(String[] args) { int[] arr = { 1, 9, 6, 4, 5 }; int[] aux = Arrays.copyOf(arr, arr.length); // получить количество инверсий, выполнив сортировку слиянием на arr System.out.println(«The inversion count is « + mergesort(arr, aux, 0, arr.length — 1)); } } |
Скачать Выполнить код
результат:
The inversion count is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
# Объединить два отсортированных подсписка `A[low … mid]` и `A[mid+1 … high]` def merge(A, aux, low, mid, high): k = i = low j = mid + 1 inversionCount = 0 # при наличии элементов в левом и правом прогонах while i <= mid and j <= high: if A[i] <= A[j]: aux[k] = A[i] i = i + 1 else: aux[k] = A[j] j = j + 1 inversionCount += (mid — i + 1) # ПРИМЕЧАНИЕ k = k + 1 # скопировать оставшиеся элементы while i <= mid: aux[k] = A[i] k = k + 1 i = i + 1 »’ no need to copy the second half (since the remaining items are already in their correct position in the temporary array) »’ # скопировать обратно в исходный список, чтобы отразить порядок сортировки for i in range(low, high + 1): A[i] = aux[i] return inversionCount # Отсортировать список `A[low…high]`, используя вспомогательный список `aux` def mergesort(A, aux, low, high): # Базовый вариант if high <= low: #, если размер прогона <= 1 return 0 # найти среднюю точку mid = low + ((high — low) >> 1) inversionCount = 0 # рекурсивно разделяет прогоны на две половины до тех пор, пока размер прогона не станет <= 1, # Затем # объединяет их и возвращает вверх по цепочке вызовов. inversionCount += mergesort(A, aux, low, mid) # разделить/объединить левую половину inversionCount += mergesort(A, aux, mid + 1, high) # разделить/объединить правую половину inversionCount += merge(A, aux, low, mid, high) # объединяет две половины пробега return inversionCount if __name__ == ‘__main__’: A = [1, 9, 6, 4, 5] aux = A.copy() # получает количество инверсий, выполняя сортировку слиянием в списке print(«Inversion count is», mergesort(A, aux, 0, len(A) — 1)) |
Скачать Выполнить код
результат:
The inversion count is 5
Временная сложность приведенного выше решения равна O(n.log(n)) (такой же, как у алгоритма сортировки слиянием), а вспомогательное пространство, используемое программой, равно O(n).
Спасибо за чтение.
Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.
Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования 
This answer contains the results of the timeit tests produced by the code in my main answer. Please see that answer for details!
count_inversions speed test results
Size = 5, hi = 2, 4096 loops
ltree_count_PM2R : 0.04871, 0.04872, 0.04876
bruteforce_loops_PM2R : 0.05696, 0.05700, 0.05776
solution_TimBabych : 0.05760, 0.05822, 0.05943
solutionE_TimBabych : 0.06642, 0.06704, 0.06760
bruteforce_sum_PM2R : 0.07523, 0.07545, 0.07563
perm_sum_PM2R : 0.09873, 0.09875, 0.09935
rank_sum_PM2R : 0.10449, 0.10463, 0.10468
solution_python : 0.13034, 0.13061, 0.13221
fenwick_inline_PM2R : 0.14323, 0.14610, 0.18802
perm_radixR_PM2R : 0.15146, 0.15203, 0.15235
merge_count_BM : 0.16179, 0.16267, 0.16467
perm_radixI_PM2R : 0.16200, 0.16202, 0.16768
perm_fenwick_PM2R : 0.16887, 0.16920, 0.17075
merge_PM2R : 0.18262, 0.18271, 0.18418
count_inversions_NiklasB : 0.19183, 0.19279, 0.20388
count_inversion_mkso : 0.20060, 0.20141, 0.20398
inv_cnt_ZheHu : 0.20815, 0.20841, 0.20906
fenwick_PM2R : 0.22109, 0.22137, 0.22379
reversePairs_nomanpouigt : 0.29620, 0.29689, 0.30293
Value: 5
Size = 10, hi = 5, 2048 loops
solution_TimBabych : 0.05954, 0.05989, 0.05991
solutionE_TimBabych : 0.05970, 0.05972, 0.05998
perm_sum_PM2R : 0.07517, 0.07519, 0.07520
ltree_count_PM2R : 0.07672, 0.07677, 0.07684
bruteforce_loops_PM2R : 0.07719, 0.07724, 0.07817
rank_sum_PM2R : 0.08587, 0.08823, 0.08864
bruteforce_sum_PM2R : 0.09470, 0.09472, 0.09484
solution_python : 0.13126, 0.13154, 0.13185
perm_radixR_PM2R : 0.14239, 0.14320, 0.14474
perm_radixI_PM2R : 0.14632, 0.14669, 0.14679
fenwick_inline_PM2R : 0.16796, 0.16831, 0.17030
perm_fenwick_PM2R : 0.18189, 0.18212, 0.18638
merge_count_BM : 0.19816, 0.19870, 0.19948
count_inversions_NiklasB : 0.21807, 0.22031, 0.22215
merge_PM2R : 0.22037, 0.22048, 0.26106
fenwick_PM2R : 0.24290, 0.24314, 0.24744
count_inversion_mkso : 0.24895, 0.24899, 0.25205
inv_cnt_ZheHu : 0.26253, 0.26259, 0.26590
reversePairs_nomanpouigt : 0.35711, 0.35762, 0.35973
Value: 20
Size = 20, hi = 10, 1024 loops
solutionE_TimBabych : 0.05687, 0.05696, 0.05720
solution_TimBabych : 0.06126, 0.06151, 0.06168
perm_sum_PM2R : 0.06875, 0.06906, 0.07054
rank_sum_PM2R : 0.07988, 0.07995, 0.08002
ltree_count_PM2R : 0.11232, 0.11239, 0.11257
bruteforce_loops_PM2R : 0.12553, 0.12584, 0.12592
solution_python : 0.13472, 0.13540, 0.13694
bruteforce_sum_PM2R : 0.15820, 0.15849, 0.16021
perm_radixI_PM2R : 0.17101, 0.17148, 0.17229
perm_radixR_PM2R : 0.17891, 0.18087, 0.18366
perm_fenwick_PM2R : 0.20554, 0.20708, 0.21412
fenwick_inline_PM2R : 0.21161, 0.21163, 0.22047
merge_count_BM : 0.24125, 0.24261, 0.24565
count_inversions_NiklasB : 0.25712, 0.25754, 0.25778
merge_PM2R : 0.26477, 0.26566, 0.31297
fenwick_PM2R : 0.28178, 0.28216, 0.29069
count_inversion_mkso : 0.30286, 0.30290, 0.30652
inv_cnt_ZheHu : 0.32024, 0.32041, 0.32447
reversePairs_nomanpouigt : 0.45812, 0.45822, 0.46172
Value: 98
Size = 40, hi = 20, 512 loops
solutionE_TimBabych : 0.05784, 0.05787, 0.05958
solution_TimBabych : 0.06452, 0.06475, 0.06479
perm_sum_PM2R : 0.07254, 0.07261, 0.07263
rank_sum_PM2R : 0.08537, 0.08540, 0.08572
ltree_count_PM2R : 0.11744, 0.11749, 0.11792
solution_python : 0.14262, 0.14285, 0.14465
perm_radixI_PM2R : 0.18774, 0.18776, 0.18922
perm_radixR_PM2R : 0.19425, 0.19435, 0.19609
bruteforce_loops_PM2R : 0.21500, 0.21511, 0.21686
perm_fenwick_PM2R : 0.23338, 0.23375, 0.23674
fenwick_inline_PM2R : 0.24947, 0.24958, 0.25189
bruteforce_sum_PM2R : 0.27627, 0.27646, 0.28041
merge_count_BM : 0.28059, 0.28128, 0.28294
count_inversions_NiklasB : 0.28557, 0.28759, 0.29022
merge_PM2R : 0.29886, 0.29928, 0.30317
fenwick_PM2R : 0.30241, 0.30259, 0.35237
count_inversion_mkso : 0.34252, 0.34356, 0.34441
inv_cnt_ZheHu : 0.37468, 0.37569, 0.37847
reversePairs_nomanpouigt : 0.50725, 0.50770, 0.50943
Value: 369
Size = 80, hi = 40, 256 loops
solutionE_TimBabych : 0.06339, 0.06373, 0.06513
solution_TimBabych : 0.06984, 0.06994, 0.07009
perm_sum_PM2R : 0.09171, 0.09172, 0.09186
rank_sum_PM2R : 0.10468, 0.10474, 0.10500
ltree_count_PM2R : 0.14416, 0.15187, 0.18541
solution_python : 0.17415, 0.17423, 0.17451
perm_radixI_PM2R : 0.20676, 0.20681, 0.20936
perm_radixR_PM2R : 0.21671, 0.21695, 0.21736
perm_fenwick_PM2R : 0.26197, 0.26252, 0.26264
fenwick_inline_PM2R : 0.28111, 0.28249, 0.28382
count_inversions_NiklasB : 0.31746, 0.32448, 0.32451
merge_count_BM : 0.31964, 0.33842, 0.35276
merge_PM2R : 0.32890, 0.32941, 0.33322
fenwick_PM2R : 0.34355, 0.34377, 0.34873
count_inversion_mkso : 0.37689, 0.37698, 0.38079
inv_cnt_ZheHu : 0.42923, 0.42941, 0.43249
bruteforce_loops_PM2R : 0.43544, 0.43601, 0.43902
bruteforce_sum_PM2R : 0.52106, 0.52160, 0.52531
reversePairs_nomanpouigt : 0.57805, 0.58156, 0.58252
Value: 1467
Size = 160, hi = 80, 128 loops
solutionE_TimBabych : 0.06766, 0.06784, 0.06963
solution_TimBabych : 0.07433, 0.07489, 0.07516
perm_sum_PM2R : 0.13143, 0.13175, 0.13179
rank_sum_PM2R : 0.14428, 0.14440, 0.14922
solution_python : 0.20072, 0.20076, 0.20084
ltree_count_PM2R : 0.20314, 0.20583, 0.24776
perm_radixI_PM2R : 0.23061, 0.23078, 0.23525
perm_radixR_PM2R : 0.23894, 0.23915, 0.24234
perm_fenwick_PM2R : 0.30984, 0.31181, 0.31503
fenwick_inline_PM2R : 0.31933, 0.32680, 0.32722
merge_count_BM : 0.36003, 0.36387, 0.36409
count_inversions_NiklasB : 0.36796, 0.36814, 0.37106
merge_PM2R : 0.36847, 0.36848, 0.37127
fenwick_PM2R : 0.37833, 0.37847, 0.38095
count_inversion_mkso : 0.42746, 0.42747, 0.43184
inv_cnt_ZheHu : 0.48969, 0.48974, 0.49293
reversePairs_nomanpouigt : 0.67791, 0.68157, 0.72420
bruteforce_loops_PM2R : 0.82816, 0.83175, 0.83282
bruteforce_sum_PM2R : 1.03322, 1.03378, 1.03562
Value: 6194
Size = 320, hi = 160, 64 loops
solutionE_TimBabych : 0.07467, 0.07470, 0.07483
solution_TimBabych : 0.08036, 0.08066, 0.08077
perm_sum_PM2R : 0.21142, 0.21201, 0.25766
solution_python : 0.22410, 0.22644, 0.22897
rank_sum_PM2R : 0.22820, 0.22851, 0.22877
ltree_count_PM2R : 0.24424, 0.24595, 0.24645
perm_radixI_PM2R : 0.25690, 0.25710, 0.26191
perm_radixR_PM2R : 0.26501, 0.26504, 0.26729
perm_fenwick_PM2R : 0.33483, 0.33507, 0.33845
fenwick_inline_PM2R : 0.34413, 0.34484, 0.35153
merge_count_BM : 0.39875, 0.39919, 0.40302
fenwick_PM2R : 0.40434, 0.40439, 0.40845
merge_PM2R : 0.40814, 0.41531, 0.51417
count_inversions_NiklasB : 0.41681, 0.42009, 0.42128
count_inversion_mkso : 0.47132, 0.47192, 0.47385
inv_cnt_ZheHu : 0.54468, 0.54750, 0.54893
reversePairs_nomanpouigt : 0.76164, 0.76389, 0.80357
bruteforce_loops_PM2R : 1.59125, 1.60430, 1.64131
bruteforce_sum_PM2R : 2.03734, 2.03834, 2.03975
Value: 24959
Run 2
Size = 640, hi = 320, 8 loops
solutionE_TimBabych : 0.04135, 0.04374, 0.04575
ltree_count_PM2R : 0.06738, 0.06758, 0.06874
perm_radixI_PM2R : 0.06928, 0.06943, 0.07019
fenwick_inline_PM2R : 0.07850, 0.07856, 0.08059
perm_fenwick_PM2R : 0.08151, 0.08162, 0.08170
perm_sum_PM2R : 0.09122, 0.09133, 0.09221
rank_sum_PM2R : 0.09549, 0.09603, 0.11270
merge_count_BM : 0.10733, 0.10807, 0.11032
count_inversions_NiklasB : 0.12460, 0.19865, 0.20205
solution_python : 0.13514, 0.13585, 0.13814
Size = 1280, hi = 640, 8 loops
solutionE_TimBabych : 0.04714, 0.04742, 0.04752
perm_radixI_PM2R : 0.15325, 0.15388, 0.15525
solution_python : 0.15709, 0.15715, 0.16076
fenwick_inline_PM2R : 0.16048, 0.16160, 0.16403
ltree_count_PM2R : 0.16213, 0.16238, 0.16428
perm_fenwick_PM2R : 0.16408, 0.16416, 0.16449
count_inversions_NiklasB : 0.19755, 0.19833, 0.19897
merge_count_BM : 0.23736, 0.23793, 0.23912
perm_sum_PM2R : 0.32946, 0.32969, 0.33277
rank_sum_PM2R : 0.34637, 0.34756, 0.34858
Size = 2560, hi = 1280, 8 loops
solutionE_TimBabych : 0.10898, 0.11005, 0.11025
perm_radixI_PM2R : 0.33345, 0.33352, 0.37656
ltree_count_PM2R : 0.34670, 0.34786, 0.34833
perm_fenwick_PM2R : 0.34816, 0.34879, 0.35214
fenwick_inline_PM2R : 0.36196, 0.36455, 0.36741
solution_python : 0.36498, 0.36637, 0.40887
count_inversions_NiklasB : 0.42274, 0.42745, 0.42995
merge_count_BM : 0.50799, 0.50898, 0.50917
perm_sum_PM2R : 1.27773, 1.27897, 1.27951
rank_sum_PM2R : 1.29728, 1.30389, 1.30448
Size = 5120, hi = 2560, 8 loops
solutionE_TimBabych : 0.26914, 0.26993, 0.27253
perm_radixI_PM2R : 0.71416, 0.71634, 0.71753
perm_fenwick_PM2R : 0.71976, 0.72078, 0.72078
fenwick_inline_PM2R : 0.72776, 0.72804, 0.73143
ltree_count_PM2R : 0.81972, 0.82043, 0.82290
solution_python : 0.83714, 0.83756, 0.83962
count_inversions_NiklasB : 0.87282, 0.87395, 0.92087
merge_count_BM : 1.09496, 1.09584, 1.10207
rank_sum_PM2R : 5.02564, 5.06277, 5.06666
perm_sum_PM2R : 5.09088, 5.12999, 5.13512
Size = 10240, hi = 5120, 8 loops
solutionE_TimBabych : 0.71556, 0.71718, 0.72201
perm_radixI_PM2R : 1.54785, 1.55096, 1.55515
perm_fenwick_PM2R : 1.55103, 1.55353, 1.59298
fenwick_inline_PM2R : 1.57118, 1.57240, 1.57271
ltree_count_PM2R : 1.76240, 1.76247, 1.80944
count_inversions_NiklasB : 1.86543, 1.86851, 1.87208
solution_python : 2.01490, 2.01519, 2.06423
merge_count_BM : 2.35215, 2.35301, 2.40023
rank_sum_PM2R : 20.07048, 20.08399, 20.13200
perm_sum_PM2R : 20.10187, 20.12551, 20.12683
Run 3
Size = 20480, hi = 10240, 4 loops
solutionE_TimBabych : 1.07636, 1.08243, 1.09569
perm_radixI_PM2R : 1.59579, 1.60519, 1.61785
perm_fenwick_PM2R : 1.66885, 1.68549, 1.71109
fenwick_inline_PM2R : 1.72073, 1.72752, 1.77217
ltree_count_PM2R : 1.96900, 1.97820, 2.02578
count_inversions_NiklasB : 2.03257, 2.05005, 2.18548
merge_count_BM : 2.46768, 2.47377, 2.52133
solution_python : 2.49833, 2.50179, 3.79819
Size = 40960, hi = 20480, 4 loops
solutionE_TimBabych : 3.51733, 3.52008, 3.56996
perm_radixI_PM2R : 3.51736, 3.52365, 3.56459
perm_fenwick_PM2R : 3.76097, 3.80900, 3.87974
fenwick_inline_PM2R : 3.95099, 3.96300, 3.99748
ltree_count_PM2R : 4.49866, 4.54652, 5.39716
count_inversions_NiklasB : 4.61851, 4.64303, 4.73026
merge_count_BM : 5.31945, 5.35378, 5.35951
solution_python : 6.78756, 6.82911, 6.98217
Size = 81920, hi = 40960, 4 loops
perm_radixI_PM2R : 7.68723, 7.71986, 7.72135
perm_fenwick_PM2R : 8.52404, 8.53349, 8.53710
fenwick_inline_PM2R : 8.97082, 8.97561, 8.98347
ltree_count_PM2R : 10.01142, 10.01426, 10.03216
count_inversions_NiklasB : 10.60807, 10.62424, 10.70425
merge_count_BM : 11.42149, 11.42342, 11.47003
solutionE_TimBabych : 12.83390, 12.83485, 12.89747
solution_python : 19.66092, 19.67067, 20.72204
Size = 163840, hi = 81920, 4 loops
perm_radixI_PM2R : 17.14153, 17.16885, 17.22240
perm_fenwick_PM2R : 19.25944, 19.27844, 20.27568
fenwick_inline_PM2R : 19.78221, 19.80219, 19.80766
ltree_count_PM2R : 22.42240, 22.43259, 22.48837
count_inversions_NiklasB : 22.97341, 23.01516, 23.98052
merge_count_BM : 24.42683, 24.48559, 24.51488
solutionE_TimBabych : 60.96006, 61.20145, 63.71835
solution_python : 73.75132, 73.79854, 73.95874
Size = 327680, hi = 163840, 4 loops
perm_radixI_PM2R : 36.56715, 36.60221, 37.05071
perm_fenwick_PM2R : 42.21616, 42.21838, 42.26053
fenwick_inline_PM2R : 43.04987, 43.09075, 43.13287
ltree_count_PM2R : 49.87400, 50.08509, 50.69292
count_inversions_NiklasB : 50.74591, 50.75012, 50.75551
merge_count_BM : 52.37284, 52.51491, 53.43003
solutionE_TimBabych : 373.67198, 377.03341, 377.42360
solution_python : 411.69178, 411.92691, 412.83856
Size = 655360, hi = 327680, 4 loops
perm_radixI_PM2R : 78.51927, 78.66327, 79.46325
perm_fenwick_PM2R : 90.64711, 90.80328, 91.76126
fenwick_inline_PM2R : 93.32482, 93.39086, 94.28880
count_inversions_NiklasB : 107.74393, 107.80036, 108.71443
ltree_count_PM2R : 109.11328, 109.23592, 110.18247
merge_count_BM : 111.05633, 111.07840, 112.05861
solutionE_TimBabych : 1830.46443, 1836.39960, 1849.53918
solution_python : 1911.03692, 1912.04484, 1914.69786
Вам сначала нужно разобраться с сортировкой слиянием, а именно понять идею алгоритма, а потом уже разбираться с инверсией.
Скажу кратко: мы разбиваем массив на две части, каждую из этих частей, в свою очередь, тоже разбиваем на две части и т.д., пока наши части не будут состоять из одного элемента.
После разбиения мы сливаем парами части в одну так, чтобы результирующая часть была отсортирована — сравниваем элементы одной части с элементами другой соответственно и записываем их в нужном порядке в результирующую. Затем полученные части мы опять попарно сольем и т.д., пока у нас не останется одна часть, которая и будет являться отсортированным массивом.
Текстом трудно понять, поэтому рекомендую посмотреть графическую демонстрацию (на той же википедии есть гифка). Когда поймете идею, уже можно вникать и в реализацию.
Насчет инверсий
Когда мы сливаем обе части, как я уже говорил, мы сравниваем элементы одной (первой, левой) части с элементами другой (правой, второй) части соответственно. И если элемент левой части больше элемента правой части соответственно, то значит это и есть инверсия.
И так же все оставшиеся элементы левой части тоже будут больше, т.к. левая и правая часть отсортированы. Поэтому количество инверсий нужно увеличить на количество оставшихся элементов + 1 (текущий элемент).
UPD:
Вот и пример.
Индексация идет с 0. Не описывал, что добавляем элементы в результирующую часть, думаю, это и так понятно. Описал только те части, в которых есть инверсии. Возможны ошибки, т.к. быстро делал. Да и пришлось так сжато уместить элементы, чтобы картинка полностью отобразилась на хэшкоде.
Материал из Algocode wiki
Перейти к: навигация, поиск
Количество инверсий
Пусть у нас есть некоторая перестановка $a$. Инверсией называется пара индексов $i$ и $j$ такая, что $i < j$ и $a[i] > a[j]$.
> Найти количество инверсий в данной перестановке.
Наивный алгоритм
Эта задача легко решается обычным перебором двух индексов за $O(n^2)$:
Реализация
1 int a[n], ans = 0; 2 3 for (int i = 0; i < n; ++i) { 4 for (int j = i + 1; j < n; ++j) { 5 if (a[i] > a[j]) { 6 ans++; 7 } 8 } 9 } 10 11 cout << ans << endl;
Алгоритм за $O(nlog(n))$
Внезапно эту задачу можно решить используя сортировку слиянием, слегка модифицируя её. Оставим ту же идею. Пусть мы умеем находить количество инверсий в массиве размера $n$, научимся находить количество инверсий в массиве размера $2n$.
Заметим, что мы уже знаем количество инверсий в левой половине и в правой половине массива. Осталось лишь посчитать число инверсий, где одно число лежит в левой половине, а второе в правой половине. Как же их посчитать?
Давайте подробнее рассмотрим операцию merge левой и правой половины (которую мы ранее заменили на вызов встроенной функции merge). Первый указатель указывает на элемент левой половины, второй указатель указывает на элемент второй половины, мы смотрим на минимум из них и этот указатель вдигаем вправо.
Рассмотрим число $A$ в левой половине. В скольких инверсиях между половинами оно участвует? В количестве, равному количеству чисел в правой половине меньше, чем оно. Знаем ли мы это количество? Да! Ровно в тот момент, когда мы число $A$ вносим в слитый массив, второй указатель указывает на первое число в правой половине, которое больше чем $A$.
Значит в тот момент, когда мы добавляем число $A$ из левой половины, к ответу достаточно прибавить индекс второго указателя (минус начало правой половины). Так мы учтем все инверсии между половинами.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin
7.4. Подсчет инверсий (скоро)
Материалы этой главы ещё в разработке.
Подпишитесь на обновления, и мы сообщим, когда они будут доступны, — или расскажем о других новостях.