Программа Python для подсчета инверсий размера три в заданном массиве
Счетчик инверсий — это метод подсчета шагов, с помощью которого мы можем вычислить количество шагов сортировки, выполненных определенным массивом. Он также способен подсчитывать время работы массива. Но если мы хотим отсортировать массив обратным образом, счетчиком будет максимальное число, присутствующее в этом массиве.
Array: { 5, 4, 3, 2, 1} // for the reverse manner
Pairs: {5, 4}, {5,3} , {3,2}, {3,1}, {2,1},{4,3}, {4,2}, {4,1},}, {5,2}, {5,1}
Output: 10
Array: {1, 2, 3, 4, 5} // for the increasing manner
Pairs: No Pairs
Output: 0
Array: {1,5,2,8,3,4}
Pairs: {5, 2}, {5, 3}, {5, 4}, {8, 3}, {8, 4}
Output: 5
Счетчик инверсии показывает, насколько далек этот конкретный массив от сортировки в порядке возрастания. Вот два конкретных процесса для описания этой ситуации с решением:
Чтобы найти меньшие элементы: Чтобы найти меньший элемент из массива, нам нужно перебрать индекс от n-1 до 0. Применяя (a[i]-1), мы можем вычислить getSum() здесь. Процесс будет выполняться до тех пор, пока не достигнет значения a[i]-1.
Чтобы найти большее число: Чтобы найти большее число по индексу, нам нужно выполнить итерацию от 0 до n-1. Для каждого элемента нам нужно выполнить расчет для каждого числа до a[i]. Вычтите его из i. Тогда мы получим число, большее a[i].
Алгоритм подсчета инверсий размера три в массиве
Вот в этом алгоритме; мы научимся считать инверсии размера три в заданном массиве в определенной среде программирования.
-
Шаг 1 — Начало
Шаг 2 — Объявите массив и счетчик инверсий (как arr[] -> array и invCount -> счетчик инверсий)
Шаг 3 — Внутренний цикл от y=x + 1 до N
Шаг 4 — Если элемент по адресу x больше, чем элемент по индексу y
Шаг 5 — Затем увеличьте invCount ++.
Шаг 6 — Распечатайте пару
Шаг 7 — Прекратить
Синтаксис для подсчета инверсий третьего размера в массиве: -
Говорят, что пара (A[i], A[j]) находится в инверсии, если: A[i] > A[j] и i < j
Реализация С++
int getInversions(int * A, int n) {
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (A[i] > a[j]) {
++count;
}
}
}
return count;
}
Java-реализация
public static int getInversions(int[] A, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (A[i] > A[j]) {
count += 1;
}
}
}
return count;
}
Реализация Python
def getInversions(A, n):
count = 0
for i in range(n):
for j in range(i + 1, n):
if A[i] > A[j]:
count += 1
return count;
Здесь мы упомянули возможные синтаксисы для подсчета инверсий третьего размера в данном массиве. И для этого метода; Временная сложность равна O(N^2), где N — общий размер массива и; Пространственная сложность: O(1), так как дополнительное пространство не использовалось.
Подходы, которым стоит следовать
Подход 1 — Подсчет инверсий размера три в заданном массиве с помощью программы для подсчета инверсий размера 3.
Подход 2 — лучший подход для подсчета инверсий размера 3
Подход 3 — Подсчет инверсий размера 3 с использованием двоичного индексированного дерева.
Подсчитайте инверсии размера три в заданном массиве с помощью программы для подсчета инверсий размера 3.
Для простого подхода к подсчету инверсий размера три нам нужно запустить цикл для всех возможных значений i, j и k. Временная сложность равна O(n^3), а O(1) отражает вспомогательное пространство.
Условие —
a[i] > a[j] > a[k] и i < j < k.
Пример 1
def getInvCount(arr):
n = len(arr)
invcount = 0
for i in range(0,n-1):
for j in range(i+1 , n):
if arr[i] > arr[j]:
for k in range(j+1 , n):
if arr[j] > arr[k]:
invcount += 1
return invcount
arr = [7 , 16, 2 , 1]
print ("Inversion Count after the operation: %d" %(getInvCount(arr)))
Выход
Inversion Count after the operation: 2
Лучший подход к подсчету инверсий размера 3
В этом методе мы будем рассматривать каждый элемент массива как средний элемент инверсии. Это помогает уменьшить сложность. Для этого подхода временная сложность равна O(n^2), а вспомогательное пространство — O(1).
Пример 2
def getInvCount(arr, n):
invcount = 0
for i in range(1,n-1):
small = 0
for j in range(i+1 ,n):
if (arr[i] > arr[j]):
small+=1
great = 0;
for j in range(i-1,-1,-1):
if (arr[i] < arr[j]):
great+=1
invcount += great * small
return invcount
arr = [8, 4, 2, 1]
n = len(arr)
print("Inversion Count After The Method Run :",getInvCount(arr, n))
Выход
Inversion Count After The Method Run : 4
Подсчитайте инверсии размера 3, используя двоичное индексированное дерево.
В этом методе мы подсчитываем как большие элементы, так и меньшие. Затем выполните операцию умножения большего[] на меньшее[] и прибавьте ее к конечному результату. Здесь временная сложность равна O(n*log(n)) и вспомогательное пространство обозначается как O(n).
Пример 3
def getSum( BITree, index):
sum = 0
while (index > 0):
sum += BITree[index]
index -= index & (-index)
return sum
def updateBIT(BITree, n, index, val):
while (index <= n):
BITree[index] += val
index += index & (-index)
def getInvCount(arr, n):
invcount = 0
maxElement = max(arr)
BIT = [0] * (maxElement + 1)
for i in range(n - 1, -1, -1):
invcount += getSum(BIT, arr[i] - 1)
updateBIT(BIT, maxElement, arr[i], 1)
return invcount
if __name__ =="__main__":
arr = [8, 4, 2, 1]
n = 4
print("Inversion Count After The Operation Done : ",
getInvCount(arr, n))
Выход
Inversion Count After The Operation Done : 6
Заключение
Из приведенного выше обсуждения мы узнали, как считать инверсии третьего размера в данном массиве. Надеюсь, что благодаря этой статье и упомянутым кодам, использующим конкретный язык, вы получили более широкое представление об этой теме.