Lo primero a tener en cuenta en este problema es que la cantidad de intercambios necesarios para ordenar una matriz es equivalente a la cantidad de inversiones en una matriz. La inversión en una matriz A[1 .. n] se define como un par (i, j) tal que i < j y A[i] > A[j] . Si la matriz no tiene inversión, se debe ordenar.
Hay dos formas de contar el número de inversiones en una matriz. Enumeraré dos soluciones a continuación, que se ejecutan en O(n log(n))
1) Modificar tipo de fusión:
- ¿Debo tomar un curso de Matemática discreta para comprender mejor las estructuras de datos?
- ¿Es malo si no entiendo un algoritmo? He estado tratando de entender algunos algoritmos (los recursivos en su mayoría), entiendo la mayoría de ellos, pero no pude entender algunos.
- ¿Qué pasaría si le preguntas a AI si sus algoritmos son autoconsistentes?
- ¿Dónde se usan realmente las estructuras de datos?
- ¿Cómo se implementa el algoritmo HITS?
Modifique el orden de fusión para que, además de ordenar su entrada, cuente el número de inversiones que estaban en esa matriz. Probémoslo por inducción.
Caso base:
Fácil: devuelve 0 inversión si el tamaño de la matriz es menor o igual que 1
Caso general:
Analicemos el problema paso a paso.
Tenemos dos matrices para fusionar. ¿Qué tipo de inversión podría haber allí? Una inversión (i, j) podría estar en la misma mitad (izquierda o mitad derecha), o podría estar en la mitad izquierda y j podría estar en la mitad derecha (no puedo estar en la mitad derecha porque tenemos la restricción i < j ). Sin embargo, según la hipótesis inductiva, el número de inversiones dentro de la mitad izquierda y derecha de la matriz sería devuelto por las respectivas llamadas recursivas a cada mitad de la matriz, por lo que solo necesitamos contar la cantidad de inversiones en las dos mitades ( i en izquierda y j en derecha).
¿Cómo contamos el número de inversiones en la matriz izquierda y derecha? En el paso de fusión del tipo de fusión, se nos da una matriz de dos tipos (izquierda y derecha). Para cada elemento left[i] en la matriz izquierda, queremos saber cuántos elementos right[j] en la matriz derecha son estrictamente más pequeños que la left[i] . Tenga en cuenta que cuando insertamos left[i] en la matriz combinada, sabemos que cada elemento a la izquierda de j es menor que left[i] (ya que se insertan en la matriz combinada antes de left[i] ). Entonces, cada vez que left[i] se inserta en la matriz combinada, incremente el contador en j . Este será el número de inversiones.
Aquí hay un código de muestra escrito en python:
def merge_sort(A): if len(A) <= 1: return 0, A middle = len(A)/2 left_inversions, left = merge_sort(A[:middle]) right_inversions, right = merge_sort(A[middle:]) merge_inversions, merged = merge(left, right) inversions = left_inversions + right_inversions + merge_inversions return inversions, merged def merge(left, right): result = [] i, j, inversions = 0, 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: inversions += j result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 inversions += j*(len(left)-i) result += left[i:] result += right[j:] return inversions, result
2) Resolver usando BIT (árbol indexado binario)
Aquí hay una forma ordenada de resolver el problema usando BIT (árbol indexado binario). BIT es una estructura de datos muy ligera que a menudo se usa para almacenar frecuencias de valores. Tiene dos operaciones básicas: suma y suma.
Cuando hay una lista [matemáticas] a_1, a_2, a_3,…, a_n [/ matemáticas]
[matemáticas] agregar (i, x): a_i = a_i + x [/ matemáticas]
[matemática] suma (i): a_1 + a_2 + a_3 +… + a_i [/ matemática]
BIT puede realizar sumas y sumas en tiempo O(log(n)) .
Si desea saber cómo funciona, aquí hay un enlace a un tutorial de TopCoder que habla sobre BIT http://community.topcoder.com/tc…
Aquí hay una implementación de muestra de BIT en Python:
class Bit: def __init__(self, n): sz = 1 while n > sz: sz *= 2 self.size =sz self.data = [0]*sz def sum(self, i): s = 0 while i > 0: s += self.data[i] i -= i & -i return s def add(self, i, x): while i < self.size: self.data[i] += x i += i & -i
¿Cómo podemos contar el número de inversiones usando BIT? Aquí está el algoritmo:
Deje que A[0 ... n-1] sea una matriz. La inversión es un par (i, j) donde i < j tal que A[i] > A[j] .
Cree un BIT de tamaño mayor que n. Iterar a través de la matriz A (sea j el índice del bucle), y para cada elemento A[j] hacer:
1) Agregue j-sum(A[j]) al número de inversiones
2) add(A[j], 1) (es decir, sumar 1 a la posición A[j] en BIT. Esto cuenta efectivamente el número de tiempo que se ve el valor A[j] hasta ahora)
¿Por qué funciona esto? Tenga en cuenta que para cada j , sum(A[j]) es el número de i tal que i < j y A[i] < A[j] , que es exactamente lo contrario de la definición de la inversión. En otras palabras, j-sum(A[j]) es el número de inversión. Tanto la suma como la suma toman O(log(m)) donde m=max(A) y se realizan n veces, por lo que el tiempo de ejecución de este algoritmo es O(n log(m)) .
Código en python:
def inversions(A): res = 0 bit = Bit(max(A)+1) for i, v in enumerate(A): res += i - bit.sum(v) bit.add(v, 1) return res
