Algoritmia: Fundamentos, Caso Peor y Operación Elemental

1. Fundamentos de los Algoritmos

Un algoritmo es una secuencia finita de instrucciones bien definidas que resuelven un problema en un número finito de pasos.

1.1. Propiedades

• Finitud: Termina tras pasos finitos.
• Definición: Instrucciones claras y precisas.
• Efectividad: Cada paso es ejecutable.
• Entrada y salida: Recibe datos y produce salida.

1.2. Ejemplos

• Búsqueda lineal: (O(n)).
• Búsqueda binaria: (O(\log n)).

2. Caso Peor (Worst Case)

El caso peor es el máximo tiempo o espacio para cualquier entrada de tamaño (n).

2.1. Definición

• Máximo número de operaciones, expresado en Big-O.
• Ejemplo: Búsqueda lineal, (O(n)).

2.2. Ejemplos

• Búsqueda lineal: (O(n)).
• Ordenamiento por inserción: (O(n^2)).

3. Operación Elemental

Operaciones básicas que toman tiempo constante, como asignaciones y comparaciones.

3.1. Definición

• Incluye asignaciones, comparaciones, accesos a arreglos.
• Cada una cuenta como 1 OE.

3.2. Ejemplo

• Búsqueda lineal: Cada comparación es una OE, total (O(n)).

4. Referencias

• Wikipedia: Algoritmo
• Tema2. Algoritmia Elemental. Resumen
• Eficiencia de los algoritmos
• Análisis de algoritmos