Eficiencia y pasos de un algoritmo repaso

¿Qué es un algoritmo?

Un algoritmo es un conjunto de instrucciones secuenciales que resuelven un problema específico.

Tipos de algoritmos

- Algoritmos de búsqueda - Algoritmos de ordenación - Algoritmos recursivos

¿Qué es la notación Big O?

La notación Big O describe la complejidad temporal o espacial de un algoritmo en función del tamaño de la entrada.

¿Verdadero o falso? Un algoritmo siempre termina.

Verdadero. Por definición, un algoritmo debe terminar tras un número finito de pasos.

Complejidad de un algoritmo

Se refiere a la cantidad de recursos necesarios para ejecutar el algoritmo: tiempo y espacio.

¿Qué es un algoritmo recursivo?

Es un algoritmo que se llama a sí mismo para resolver subproblemas del problema original.

Complejidad temporal: $\displaystyle O(n)$

Indica que el tiempo de ejecución aumenta linealmente con el tamaño de la entrada.

Comparación: algoritmo de búsqueda lineal vs binaria.

Búsqueda lineal: $\displaystyle O(n)$; Búsqueda binaria: $\displaystyle O( ext{log } n)$.

Llenar el espacio en blanco: Un algoritmo debe ser _____ y _____

Un algoritmo debe ser claro y finito.

¿Qué define un algoritmo eficiente?

Un algoritmo eficiente minimiza el tiempo de ejecución y el uso de recursos.

Ejemplo de algoritmo simple

Para sumar dos números: 1. Leer A, B. 2. Sumar A + B. 3. Mostrar resultado.

Diferencia entre algoritmo y programa

Un algoritmo es una solución abstracta; un programa es la implementación del algoritmo en un lenguaje de programación.

¿Qué es un pseudocódigo?

El pseudocódigo es una representación de un algoritmo en lenguaje natural que describe los pasos de manera informal.

¿Verdadero o falso? Todos los algoritmos son secuenciales.

Falso. Los algoritmos pueden ser secuenciales, ramificados o iterativos.

¿Qué es un algoritmo iterativo?

Es un algoritmo que utiliza bucles para repetir un conjunto de instrucciones hasta cumplir una condición.

Ejemplo de notación de un algoritmo

Inicio: Leer N; Para i desde 1 hasta N: Sumar i; Fin.

¿Qué es la complejidad temporal?

Es la medida del tiempo que un algoritmo tarda en completarse según el tamaño de la entrada.

Complejidad espacial

Es la cantidad de memoria que utiliza un algoritmo en función del tamaño de la entrada.

O(1)

Indica que el tiempo de ejecución es constante, independiente del tamaño de la entrada.

O(n)

El tiempo de ejecución crece linealmente con el tamaño de la entrada. Ejemplo: recorrer un array.

O(n^2)

El tiempo de ejecución crece cuadráticamente. Ejemplo: algoritmo de burbuja, comparaciones anidadas.

Verdadero o falso: O(log n) es mejor que O(n).

Verdadero. O(log n) indica que el algoritmo se ejecuta mucho más rápido que O(n) para grandes entradas.

Comparación: Búsqueda lineal vs Búsqueda binaria.

Búsqueda lineal: O(n). Búsqueda binaria: O(log n). La segunda es más eficiente en listas ordenadas.

¿Qué significa 'exponencial' en complejidad?

Se refiere a un crecimiento muy rápido del tiempo de ejecución, como O(2^n).

¿Qué es la notación asintótica?

Es una forma de describir la complejidad de un algoritmo en el límite cuando el tamaño de entrada tiende a infinito.

Complejidad de espacio O(n)

El algoritmo utiliza espacio proporcional al tamaño de la entrada, como un array que guarda n elementos.

¿Qué describe un caso peor?

Es el tiempo máximo que puede tardar un algoritmo, considerando la entrada más desfavorable.

Rango de la notación Big O

Escribe el peor de los casos, por ejemplo, O(n) es mejor que O(n^2) en eficiencia.

Diferencia: Complejidad temporal y espacial.

Temporal: tiempo de ejecución. Espacial: memoria utilizada por el algoritmo.

Ejemplo de algoritmo O(log n)

La búsqueda binaria en un array ordenado, que divide la lista en mitades cada vez.

Razonamiento detrás de O(n log n)

Común en algoritmos de ordenación eficientes, como Merge Sort o Quick Sort.

¿Qué se entiende por 'ajuste de complejidad'?

Es la práctica de optimizar un algoritmo para mejorar su rendimiento en tiempo y espacio.

¿Qué es un algoritmo ineficiente?

Uno que tiene una alta complejidad temporal o espacial, lo que lo hace lento o que consume mucha memoria.

Complejidad constante vs lineal

Constante (O(1)): no depende de la entrada. Lineal (O(n)): depende del tamaño de la entrada.

Rango de tiempos de ejecución

- O(1) -> O(log n) -> O(n) -> O(n log n) -> O(n^2) -> O(2^n)

¿Qué indica la notación Big O?

Describe el comportamiento de un algoritmo en función del tamaño de la entrada, centrándose en el caso peor. Ejemplo: O(n) indica que el tiempo de ejecución crece linealmente con respecto al tamaño de la entrada.

Definición de problema.

Un problema es una situación que requiere una solución específica. Puede involucrar datos y operaciones a realizar.

Pasos en la resolución de problemas.

1. Definición del problema 2. Análisis 3. Diseño del algoritmo 4. Implementación 5. Pruebas 6. Documentación

Verdadero o falso: El análisis se hace después del diseño.

Falso. El análisis se realiza antes del diseño para entender el problema.

¿Qué se busca en el análisis?

Identificar requisitos, restricciones y posibles soluciones. Se debe comprender el problema a fondo.

Ejemplo de implementación.

Dado el problema: Ordenar la lista [3, 1, 2]. Uso del algoritmo de burbuja: 1. Comparar 3 y 1, intercambiar. 2. Comparar 3 y 2, intercambiar. Lista final: [1, 2, 3].

Comparación: Diseño vs Implementación.

Diseño: Crear el algoritmo en pseudocódigo. Implementación: Traducir pseudocódigo a un lenguaje de programación.

Completar: La _______ consiste en evaluar el algoritmo.

La prueba consiste en evaluar el algoritmo. Es crucial para asegurar que funcione correctamente.

¿Qué se documenta?

Se documentan las decisiones tomadas, el funcionamiento del algoritmo y cualquier limitación o mejora futura.

Causa → Efecto: Buen diseño.

Causa: Un buen diseño Efecto: Un algoritmo más eficiente y fácil de implementar.

Ejemplo de un problema complejo.

Problema: Encontrar el camino más corto en un grafo. Pasos implicados: 1. Definición del grafo 2. Análisis del algoritmo de Dijkstra 3. Implementación y pruebas.

Fase crítica: Análisis.

Es esencial para descomponer el problema. Se identifican variables y se establece un enfoque para la solución.

El algoritmo se prueba en fase...

Durante la fase de pruebas, se verifica que el algoritmo funcione con diferentes entradas y cumpla su función.

¿Qué es un algoritmo de búsqueda?

Un algoritmo diseñado para encontrar un elemento específico en una colección de datos. Ejemplos: búsqueda lineal y búsqueda binaria.

Comparación: algoritmos de ordenación vs búsqueda.

Ordenación: organiza datos. Búsqueda: encuentra datos. Ambos son fundamentales en la manipulación de datos.

Llenar el espacio: algoritmo de búsqueda _____ ayuda a encontrar un elemento en una lista ordenada.

bina

Verdadero o falso: Todos los algoritmos de ordenación son recursivos.

Falso. Existen algoritmos de ordenación iterativos como el método burbuja.

Ejemplo de algoritmo recursivo: _____ de Fibonacci.

Cálculo de la serie de Fibonacci: $\displaystyle F(n) = F(n-1) + F(n-2)$ con $\displaystyle F(0)=0$, $\displaystyle F(1)=1$.

¿Qué caracteriza a un algoritmo de ordenación?

Organiza datos en un cierto orden (ascendente o descendente). Ejemplos: Quicksort, Mergesort, Heapsort.

Causa → Efecto: ¿Qué sucede si no se ordenan los datos antes de buscar?

La búsqueda puede ser ineficiente, especialmente en grandes conjuntos de datos.

¿Cómo se clasifica un algoritmo de búsqueda recursivo?

Se clasifica como búsqueda binaria, que divide el espacio de datos en mitades para reducir pasos.