Алгоритмы и структуры данных

Подсчет инверсий

Счетчик инверсий для массива указывает, насколько далеко (или близко) находится массив от сортировки. Если массив уже отсортирован, то счетчик инверсий равен 0, но если массив отсортирован в обратном порядке, счетчик инверсий будет максимальным.

Алгоритм:
1. Создайте функцию merge, которая подсчитывает количество инверсий при слиянии двух половин массива.
⁃ Создайте два индекса i и j, i — индекс первой половины, а j — индекс второй половины.
⁃ Если a[i] больше, чем a[j], то происходят инверсии (mid – i), поскольку левый и правый подмассивы отсортированы, поэтому все оставшиеся элементы в левом подмассиве (a[i+1], a[i +2] … a[mid]) будет больше, чем a[j].
2. Создайте рекурсивную функцию, чтобы разделить массив пополам и найти ответ, суммируя количество инверсий в первой половине, количество инверсий во второй половине и количество инверсий путем слияния двух.

Сложность: O(N^2)

www.tgoop.com/the_algorithms/4671

5.3K viewsJan 17, 2024 at 09:00

Подсчет инверсий

Счетчик инверсий для массива указывает, насколько далеко (или близко) находится массив от сортировки. Если массив уже отсортирован, то счетчик инверсий равен 0, но если массив отсортирован в обратном порядке, счетчик инверсий будет максимальным.

Алгоритм:
1. Создайте функцию merge, которая подсчитывает количество инверсий при слиянии двух половин массива.
⁃ Создайте два индекса i и j, i — индекс первой половины, а j — индекс второй половины.
⁃ Если a[i] больше, чем a[j], то происходят инверсии (mid – i), поскольку левый и правый подмассивы отсортированы, поэтому все оставшиеся элементы в левом подмассиве (a[i+1], a[i +2] … a[mid]) будет больше, чем a[j].
2. Создайте рекурсивную функцию, чтобы разделить массив пополам и найти ответ, суммируя количество инверсий в первой половине, количество инверсий во второй половине и количество инверсий путем слияния двух.

Сложность: O(N^2)

BY Алгоритмы и структуры данных