Capítulo 3: Eficiencia del Algoritmo
3.4 Problemas de Práctica
Consolidemos nuestro aprendizaje con algunos problemas de práctica. Estos problemas están diseñados para ayudarte a pensar en cómo funcionan los algoritmos y practicar el análisis de su eficiencia en términos de complejidad temporal y espacial. Para cada problema, intenta escribir el pseudocódigo, determinar la complejidad temporal y espacial, y explicar tu razonamiento.
Búsqueda Lineal:
- Implementa una función
linear_search(lista, elemento)que tome una lista y un elemento, y devuelva el índice del elemento si se encuentra en la lista, y -1 en caso contrario. - Ejemplo de entrada:
linear_search([1, 3, 5, 7, 9], 5) - Ejemplo de salida:
2 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Este problema se puede resolver iterando a través de la lista dada y comprobando si cada elemento es igual al elemento objetivo.
def linear_search(list, item):
for i in range(len(list)):
if list[i] == item:
return i
return -1Complejidad Temporal: O(n) - En el peor de los casos, necesitamos recorrer cada elemento de la lista.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Suma de Elementos:
- Escribe una función
sum_elements(lista)que tome una lista de números y devuelva la suma de todos los elementos en la lista. - Ejemplo de entrada:
sum_elements([1, 2, 3, 4, 5]) - Ejemplo de salida:
15 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Simplemente podemos iterar a través de la lista y agregar cada elemento a un total en ejecución.
def sum_elements(list):
total = 0
for item in list:
total += item
return totalComplejidad Temporal: O(n) - Necesitamos revisar cada elemento en la lista.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Encontrar Duplicado:
- Implementa una función
find_duplicate(lista)que tome una lista y devuelva el primer elemento duplicado que encuentre. Si no hay duplicados, debería devolver None. - Ejemplo de entrada:
find_duplicate([1, 2, 3, 4, 2, 5]) - Ejemplo de salida:
2 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Podemos usar un conjunto para rastrear los elementos que hemos visto hasta ahora. Cuando encontramos un elemento que ya está en el conjunto, sabemos que es un duplicado.
def find_duplicate(list):
seen = set()
for item in list:
if item in seen:
return item
seen.add(item)
return NoneComplejidad Temporal: O(n^2) - En el peor de los casos, necesitamos recorrer la lista varias veces, lo que resulta en un tiempo cuadrático.
Complejidad Espacial: O(1) - No estamos utilizando memoria adicional que crezca con el tamaño de la entrada.
Bubble Sort:
- Escribe una función
bubble_sort(lista)que ordene una lista de números utilizando el algoritmo de ordenamiento de burbuja. - Ejemplo de entrada:
bubble_sort([5, 1, 4, 2, 8]) - Ejemplo de salida:
[1, 2, 4, 5, 8] - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Podemos implementar el algoritmo de ordenamiento de burbuja, que recorre repetidamente la lista, compara elementos adyacentes y los intercambia si están en el orden incorrecto.
def bubble_sort(list):
n = len(list)
for i in range(n):
for j in range(0, n - i - 1):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
return listComplejidad Temporal: O(n^2) - Por cada elemento, necesitamos compararlo con cada otro elemento.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Recuerda que, al resolver estos problemas, no solo debes pensar en la solución correcta, sino también en la eficiencia de tu solución. Intenta optimizar tus soluciones tanto para el tiempo como para el espacio cuando sea posible. Considera casos extremos, como qué sucede si la lista de entrada está vacía, o si todos los elementos en la lista son iguales.
Después de trabajar en estos problemas, deberías tener un mejor entendimiento sobre el análisis práctico de la eficiencia de los algoritmos y estar listo para enfrentar problemas y algoritmos más complejos.
3.4 Problemas de Práctica
Consolidemos nuestro aprendizaje con algunos problemas de práctica. Estos problemas están diseñados para ayudarte a pensar en cómo funcionan los algoritmos y practicar el análisis de su eficiencia en términos de complejidad temporal y espacial. Para cada problema, intenta escribir el pseudocódigo, determinar la complejidad temporal y espacial, y explicar tu razonamiento.
Búsqueda Lineal:
- Implementa una función
linear_search(lista, elemento)que tome una lista y un elemento, y devuelva el índice del elemento si se encuentra en la lista, y -1 en caso contrario. - Ejemplo de entrada:
linear_search([1, 3, 5, 7, 9], 5) - Ejemplo de salida:
2 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Este problema se puede resolver iterando a través de la lista dada y comprobando si cada elemento es igual al elemento objetivo.
def linear_search(list, item):
for i in range(len(list)):
if list[i] == item:
return i
return -1Complejidad Temporal: O(n) - En el peor de los casos, necesitamos recorrer cada elemento de la lista.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Suma de Elementos:
- Escribe una función
sum_elements(lista)que tome una lista de números y devuelva la suma de todos los elementos en la lista. - Ejemplo de entrada:
sum_elements([1, 2, 3, 4, 5]) - Ejemplo de salida:
15 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Simplemente podemos iterar a través de la lista y agregar cada elemento a un total en ejecución.
def sum_elements(list):
total = 0
for item in list:
total += item
return totalComplejidad Temporal: O(n) - Necesitamos revisar cada elemento en la lista.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Encontrar Duplicado:
- Implementa una función
find_duplicate(lista)que tome una lista y devuelva el primer elemento duplicado que encuentre. Si no hay duplicados, debería devolver None. - Ejemplo de entrada:
find_duplicate([1, 2, 3, 4, 2, 5]) - Ejemplo de salida:
2 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Podemos usar un conjunto para rastrear los elementos que hemos visto hasta ahora. Cuando encontramos un elemento que ya está en el conjunto, sabemos que es un duplicado.
def find_duplicate(list):
seen = set()
for item in list:
if item in seen:
return item
seen.add(item)
return NoneComplejidad Temporal: O(n^2) - En el peor de los casos, necesitamos recorrer la lista varias veces, lo que resulta en un tiempo cuadrático.
Complejidad Espacial: O(1) - No estamos utilizando memoria adicional que crezca con el tamaño de la entrada.
Bubble Sort:
- Escribe una función
bubble_sort(lista)que ordene una lista de números utilizando el algoritmo de ordenamiento de burbuja. - Ejemplo de entrada:
bubble_sort([5, 1, 4, 2, 8]) - Ejemplo de salida:
[1, 2, 4, 5, 8] - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Podemos implementar el algoritmo de ordenamiento de burbuja, que recorre repetidamente la lista, compara elementos adyacentes y los intercambia si están en el orden incorrecto.
def bubble_sort(list):
n = len(list)
for i in range(n):
for j in range(0, n - i - 1):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
return listComplejidad Temporal: O(n^2) - Por cada elemento, necesitamos compararlo con cada otro elemento.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Recuerda que, al resolver estos problemas, no solo debes pensar en la solución correcta, sino también en la eficiencia de tu solución. Intenta optimizar tus soluciones tanto para el tiempo como para el espacio cuando sea posible. Considera casos extremos, como qué sucede si la lista de entrada está vacía, o si todos los elementos en la lista son iguales.
Después de trabajar en estos problemas, deberías tener un mejor entendimiento sobre el análisis práctico de la eficiencia de los algoritmos y estar listo para enfrentar problemas y algoritmos más complejos.
3.4 Problemas de Práctica
Consolidemos nuestro aprendizaje con algunos problemas de práctica. Estos problemas están diseñados para ayudarte a pensar en cómo funcionan los algoritmos y practicar el análisis de su eficiencia en términos de complejidad temporal y espacial. Para cada problema, intenta escribir el pseudocódigo, determinar la complejidad temporal y espacial, y explicar tu razonamiento.
Búsqueda Lineal:
- Implementa una función
linear_search(lista, elemento)que tome una lista y un elemento, y devuelva el índice del elemento si se encuentra en la lista, y -1 en caso contrario. - Ejemplo de entrada:
linear_search([1, 3, 5, 7, 9], 5) - Ejemplo de salida:
2 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Este problema se puede resolver iterando a través de la lista dada y comprobando si cada elemento es igual al elemento objetivo.
def linear_search(list, item):
for i in range(len(list)):
if list[i] == item:
return i
return -1Complejidad Temporal: O(n) - En el peor de los casos, necesitamos recorrer cada elemento de la lista.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Suma de Elementos:
- Escribe una función
sum_elements(lista)que tome una lista de números y devuelva la suma de todos los elementos en la lista. - Ejemplo de entrada:
sum_elements([1, 2, 3, 4, 5]) - Ejemplo de salida:
15 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Simplemente podemos iterar a través de la lista y agregar cada elemento a un total en ejecución.
def sum_elements(list):
total = 0
for item in list:
total += item
return totalComplejidad Temporal: O(n) - Necesitamos revisar cada elemento en la lista.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Encontrar Duplicado:
- Implementa una función
find_duplicate(lista)que tome una lista y devuelva el primer elemento duplicado que encuentre. Si no hay duplicados, debería devolver None. - Ejemplo de entrada:
find_duplicate([1, 2, 3, 4, 2, 5]) - Ejemplo de salida:
2 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Podemos usar un conjunto para rastrear los elementos que hemos visto hasta ahora. Cuando encontramos un elemento que ya está en el conjunto, sabemos que es un duplicado.
def find_duplicate(list):
seen = set()
for item in list:
if item in seen:
return item
seen.add(item)
return NoneComplejidad Temporal: O(n^2) - En el peor de los casos, necesitamos recorrer la lista varias veces, lo que resulta en un tiempo cuadrático.
Complejidad Espacial: O(1) - No estamos utilizando memoria adicional que crezca con el tamaño de la entrada.
Bubble Sort:
- Escribe una función
bubble_sort(lista)que ordene una lista de números utilizando el algoritmo de ordenamiento de burbuja. - Ejemplo de entrada:
bubble_sort([5, 1, 4, 2, 8]) - Ejemplo de salida:
[1, 2, 4, 5, 8] - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Podemos implementar el algoritmo de ordenamiento de burbuja, que recorre repetidamente la lista, compara elementos adyacentes y los intercambia si están en el orden incorrecto.
def bubble_sort(list):
n = len(list)
for i in range(n):
for j in range(0, n - i - 1):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
return listComplejidad Temporal: O(n^2) - Por cada elemento, necesitamos compararlo con cada otro elemento.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Recuerda que, al resolver estos problemas, no solo debes pensar en la solución correcta, sino también en la eficiencia de tu solución. Intenta optimizar tus soluciones tanto para el tiempo como para el espacio cuando sea posible. Considera casos extremos, como qué sucede si la lista de entrada está vacía, o si todos los elementos en la lista son iguales.
Después de trabajar en estos problemas, deberías tener un mejor entendimiento sobre el análisis práctico de la eficiencia de los algoritmos y estar listo para enfrentar problemas y algoritmos más complejos.
3.4 Problemas de Práctica
Consolidemos nuestro aprendizaje con algunos problemas de práctica. Estos problemas están diseñados para ayudarte a pensar en cómo funcionan los algoritmos y practicar el análisis de su eficiencia en términos de complejidad temporal y espacial. Para cada problema, intenta escribir el pseudocódigo, determinar la complejidad temporal y espacial, y explicar tu razonamiento.
Búsqueda Lineal:
- Implementa una función
linear_search(lista, elemento)que tome una lista y un elemento, y devuelva el índice del elemento si se encuentra en la lista, y -1 en caso contrario. - Ejemplo de entrada:
linear_search([1, 3, 5, 7, 9], 5) - Ejemplo de salida:
2 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Este problema se puede resolver iterando a través de la lista dada y comprobando si cada elemento es igual al elemento objetivo.
def linear_search(list, item):
for i in range(len(list)):
if list[i] == item:
return i
return -1Complejidad Temporal: O(n) - En el peor de los casos, necesitamos recorrer cada elemento de la lista.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Suma de Elementos:
- Escribe una función
sum_elements(lista)que tome una lista de números y devuelva la suma de todos los elementos en la lista. - Ejemplo de entrada:
sum_elements([1, 2, 3, 4, 5]) - Ejemplo de salida:
15 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Simplemente podemos iterar a través de la lista y agregar cada elemento a un total en ejecución.
def sum_elements(list):
total = 0
for item in list:
total += item
return totalComplejidad Temporal: O(n) - Necesitamos revisar cada elemento en la lista.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Encontrar Duplicado:
- Implementa una función
find_duplicate(lista)que tome una lista y devuelva el primer elemento duplicado que encuentre. Si no hay duplicados, debería devolver None. - Ejemplo de entrada:
find_duplicate([1, 2, 3, 4, 2, 5]) - Ejemplo de salida:
2 - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Podemos usar un conjunto para rastrear los elementos que hemos visto hasta ahora. Cuando encontramos un elemento que ya está en el conjunto, sabemos que es un duplicado.
def find_duplicate(list):
seen = set()
for item in list:
if item in seen:
return item
seen.add(item)
return NoneComplejidad Temporal: O(n^2) - En el peor de los casos, necesitamos recorrer la lista varias veces, lo que resulta en un tiempo cuadrático.
Complejidad Espacial: O(1) - No estamos utilizando memoria adicional que crezca con el tamaño de la entrada.
Bubble Sort:
- Escribe una función
bubble_sort(lista)que ordene una lista de números utilizando el algoritmo de ordenamiento de burbuja. - Ejemplo de entrada:
bubble_sort([5, 1, 4, 2, 8]) - Ejemplo de salida:
[1, 2, 4, 5, 8] - Piensa en: ¿Cuál es la complejidad temporal y espacial de tu implementación?
Solución:
Podemos implementar el algoritmo de ordenamiento de burbuja, que recorre repetidamente la lista, compara elementos adyacentes y los intercambia si están en el orden incorrecto.
def bubble_sort(list):
n = len(list)
for i in range(n):
for j in range(0, n - i - 1):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
return listComplejidad Temporal: O(n^2) - Por cada elemento, necesitamos compararlo con cada otro elemento.
Complejidad Espacial: O(1) - No estamos creando ninguna nueva estructura de datos que crezca con el tamaño de la entrada.
Recuerda que, al resolver estos problemas, no solo debes pensar en la solución correcta, sino también en la eficiencia de tu solución. Intenta optimizar tus soluciones tanto para el tiempo como para el espacio cuando sea posible. Considera casos extremos, como qué sucede si la lista de entrada está vacía, o si todos los elementos en la lista son iguales.
Después de trabajar en estos problemas, deberías tener un mejor entendimiento sobre el análisis práctico de la eficiencia de los algoritmos y estar listo para enfrentar problemas y algoritmos más complejos.