PDF de programaci贸n - Algoritmos con Python - Arrays

Im谩gen de pdf Algoritmos con Python - Arrays

Algoritmos con Python - Arraysgr谩fica de visualizaciones

Publicado el 7 de Marzo del 2021
219 visualizaciones desde el 7 de Marzo del 2021
189,3 KB
16 paginas
Creado hace 43d (01/03/2021)
Algoritmos con Python

Arrays

1 de marzo de 2021

脥ndice

1 Fusi贸n de listas ordenadas

1.1 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Aplicaci贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Algoritmo en tiempo lineal
. . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Variante con k Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Suma sobre un rango

2.1 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Estructura de datos en O(1) por solicitud e inicializaci贸n en O(n) . . . . . . .

3 Duplicados en un rango

3.1 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Estructura de datos en O(1) por solicitud e inicializaci贸n en O(n) . . . . . . .

4 Suma m谩xima de los subarrays

4.1 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Algoritmo en O(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Consulta del m铆nimo de un 谩rbol de segmentos de rango

5.1 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Estructura de datos con O(log n) por solicitud . . . . . . . . . . . . . . . . .
5.4 An谩lisis de la complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
2
2
3

4
4
4

5
5
5

6
6
6
6

7
7
7
7
8

6 Consultar suma sobre un rango--脕rbol de Fenwick

10
6.1 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2 Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.3 Estructura de datos con O(log n) por solicitud . . . . . . . . . . . . . . . . . 10

7 Ventanas con k elementos distintos

13
7.1 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.2 Aplicaci贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.3 Algoritmo en O(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.4 Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

I

Introducci贸n

Los arrays 铿乬uran como uno de los tipos de datos elementales m谩s importantes. Para mu-
chos problemas simples, no se requiere ninguna otra estructura de datos. En Python, los
arrays se almacenan en el tipo de datos llamado lista. La elecci贸n de este nombre puede
resultar confusa, porque las listas de Python no tienen nada que ver con las listas enla-
zadas, que son objetos est谩ndar en C++ (std::list) y Java (LinkedList). Normalmente,
una lista enlazada permite eliminar o insertar un elemento determinado en una posici贸n
determinada en tiempo constante. Sin embargo, insertar en una lista de Python requiere
construir en tiempo lineal una nueva lista que consta de un pre铿乯o, el nuevo elemento y
un su铿乯o. Los elementos de una lista de Python se indexan desde 0. Esto debe tenerse en
cuenta al leer o mostrar datos, si alguna vez la numeraci贸n de los elementos comienza en
1 en el formato de las entradas o salidas.

En lo que sigue, usamos 鈥檃rray鈥 como t茅rmino gen茅rico independiente del lenguaje, y
鈥檒ista鈥 cuando nos referimos a la estructura de datos espec铆铿乧a de Python.

Se puede usar un array para representar un 谩rbol binario de una manera muy simple. El
padre de un nodo en el 铆ndice i se encuentra en I/2, su hijo izquierdo en el 铆ndice 2i y
su hijo derecho en el 铆ndice 2i + 1. La ra铆z est谩 en el 铆ndice 1 y el elemento en el 铆ndice 0
simplemente se ignora.

Esta secci贸n trata sobre problemas cl谩sicos en arrays y presenta estructuras de datos
para realizar operaciones en intervalos de 铆ndices conocidos como rangos, por ejemplo, el
c谩lculo de un valor m铆nimo dentro de un rango. Dos de las secciones describen estructuras
de datos din谩micas utilizadas para proporcionar operaciones e铿乧ientes de modi铿乧aci贸n de
elementos y consultas sobre dichos rangos.

1

1. Fusi贸n de listas ordenadas

1.1. De铿乶ici贸n

Dadas dos listas ordenadas x e y, producir una lista ordenada z, que contenga los elemen-
tos de x e y.

1.2. Aplicaci贸n

Esta operaci贸n es 煤til para el algoritmo de ordenaci贸n por fusi贸n. Para ordenar una lis-
ta, la dividimos en dos partes de igual tama帽o (hasta una diferencia de un elemento si
la longitud es impar). A continuaci贸n, las dos porciones se ordenan recursivamente y los
resultados ordenados se combinan mediante el procedimiento que se describe a continua-
ci贸n. Este algoritmo tiene una complejidad 贸ptima de O(n log n) comparaciones.

1.3. Algoritmo en tiempo lineal

La soluci贸n consiste en recorrer conjuntamente las dos listas e ir construyendo z a medida
que avanzamos. La clave es avanzar en cada paso dentro de la lista que tenga el elemento
actual m谩s peque帽o. Esto asegura que el propio resultado estar谩 ordenado.

Figura 1: Fusi贸n de listas

La fusi贸n de dos listas funciona un poco como una cremallera con selecci贸n m铆nima en lugar de alternancia

def merge(x, y):

z = []
i = 0
j = 0
while i < len(x) or j < len(y):

if j == len(y) or i < len(x) and x[i] <= y[j]:

# priority on x

z.append(x[i])

2

i += 1

else:

z.append(y[j])
j += 1

return z

1.4. Variante con k Listas

# now y

Para identi铿乧ar r谩pidamente la lista en la que tenemos que avanzar, podemos almacenar
los k elementos actuales de cada lista en una cola de prioridad. La complejidad es entonces
O(n log k) donde n es la longitud de la lista resultante.

3

2. Suma sobre un rango

2.1. De铿乶ici贸n

Cada petici贸n tiene la forma de un intervalo de 铆ndices [i,j) y debe devolver la suma de
los elementos de t entre los 铆ndices i (incluidos) y j (excluidos).

2.2. Estructura de datos en O(1) por solicitud e inicializaci贸n en

O(n)

Basta con calcular un array s de tama帽o n + 1, que contiene todas las sumas de pre铿乯os
de t. M谩s concretamente, s[j] = 危i<jt[i]. En particular, s[0] = 0, s[1] = t[0], s[n] =
危n鈭1

i=0 t[i]. Entonces la respuesta a la petici贸n [i,j) es s[j] - s[i].

4

3. Duplicados en un rango

3.1. De铿乶ici贸n

Cada petici贸n tiene la forma de un intervalo de 铆ndices [i,j) y debemos encontrar un
elemento x de t que aparezca al menos dos veces dentro de este intervalo o anunciar que
todos los elementos son distintos.

3.2. Estructura de datos en O(1) por solicitud e inicializaci贸n en

O(n)

Con un barrido de izquierda a derecha, construimos un array p indicando para cada j el
mayor 铆ndice i < j tal que t[i] = t[j]. Cuando t[j] se ve por primera vez, ponemos
p[j] = -1.

El c谩lculo de p requiere almacenar, para cada elemento x, el 铆ndice de la 煤ltima aparici贸n
de x observada en t durante el barrido. Esto puede hacerse con un array si se garantiza
el dominio de los elementos de t, o en su defecto con un diccionario basado en una tabla
hash.

Paralelamente, almacenamos en un array q, para cada j, el mayor valor de p[i] para todo
i j . En respuesta a una petici贸n [i,j), si alguna vez q[j - 1] < i entonces todos los
elementos de [i,j) son distintos, en caso contrario t[q[j - 1]] es un duplicado.

Para determinar los 铆ndices de dos ocurrencias, basta con calcular en paralelo con q[j] el
铆ndice i que realiza el m谩ximo.

Figura 2: Encontrar duplicados

El algoritmo para encontrar duplicados en un ejemplo. En el intervalo [3,6) todos los elementos de t son
distintos porque q[5] < 3. Sin embargo, el intervalo [4,10) contiene duplicados, por ejemplo, b en las
posiciones q[9] y p[q[9]].

5

4. Suma m谩xima de los subarrays

4.1. De铿乶ici贸n

Este problema estad铆stico busca encontrar, para un array de valores t, el m谩ximo de t[i] +
t[i + 1] + 路路路 + t[j] sobre cada par de 铆ndices i,j con i j .

4.2. Algoritmo en O(n)

Esta soluci贸n por programaci贸n din谩mica fue encontrada por Jay Kadane en 1984. Para
cada 铆ndice j buscamos la suma m谩xima t[i] + 路路路 + t[j] sobre todos los 铆ndices 0 i j
. Denotemos A[j] como este valor. Este valor debe ser el propio t[j], o estar formado por
t[j] m谩s una suma de la forma t[i] + 路路路 + t[j 鈭 1], que es a su vez m谩xima. Por tanto,
A[0] = t[0], ya que es la 煤nica opci贸n, y para j 1, tenemos la relaci贸n de recurrencia
A[j] = t[j] + max{A[j - 1], 0}.

4.3. Variantes

Este problema se puede generalizar a las matrices. Dada una matriz M de dimensi贸n n
x m, un rango de 铆ndices de 铿乴a [a,b] y un rango de 铆ndices de columna [i,j] de铿乶en
un rect谩ngulo [a, b] 鈯 [i, j] dentro de la matriz. Queremos encontrar el rect谩ngulo con la
mayor suma. Para ello, basta con hacer un bucle sobre todos los pares de 铆ndices de 铿乴a
[a, b], a b, y para cada par generar un array t de longitud m, tal que t[i] = M[a, i] +
路路路 + M[b, i]. Esta matriz puede obtenerse en tiempo O(m) a partir de la matriz de la
iteraci贸n anterior correspondiente al par [a, b - 1], simplemente a帽adiendo la 铿乴a b de
M. Con la ayuda del algoritmo anterior, podemos encontrar en tiempo O(m) un rango de
columnas [i,j] que describa un rect谩ngulo [a, b]鈯 [i, j] de suma m谩xima acotada por las
铿乴as a y b. La mayor suma observada al hacer un bucle sobre a y b da la suma m谩xima de
M. Este enfoque produce una soluci贸n con complejidad O(n2m).

6

5. Consulta del m铆nimo de un 谩rbol de segmentos de

rango

5.1. De铿乶ici贸n

Deseamos mantener una estructura de datos que almacene un array t de n valores y que
permita las siguientes operaciones:

Cambiar t[i] para un 铆ndice i dado.

Calcular minij<kt[j] para un rango dado de 铆ndices i,k.

5.2. Variante

Con s贸lo unos peque帽os cambios tambi茅n podemos determinar el 铆ndice del elemento
m铆nimo junto con su valor.

5.3. Estructura de datos con O(log n) por solicitud

La idea es complementar la matriz t con un 谩rbol binario, conocido como 谩rbol de segmen-
tos. Esta estructura de datos tambi茅n se conoce como 谩rbol BIT (Binary Index Tree). Cada
nodo es responsable de un rango de 铆ndices en t, v茅ase la 铿乬ura 3. El tama帽o
  • Links de descarga
http://lwp-l.com/pdf18967

Comentarios de: Algoritmos con Python - Arrays (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoraci贸n
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar im谩genes, archivos y/o videos.

Puedes registrarte o validarte desde aqu铆.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
gui帽o
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad