Introducción a la clase
En esta clase aprenderemos sobre la complejidad algorítmica, un concepto fundamental para medir la eficiencia de un algoritmo. Analizaremos cómo se mide el rendimiento del código usando la Notación Big O y cómo impacta en el desarrollo de software en C#.
¿Qué obtendrás de esta clase?
- Comprender qué es la complejidad algorítmica y su importancia.
- Aprender a medir la eficiencia de un algoritmo con Big O Notation.
- Identificar los diferentes tipos de complejidad.
- Implementar ejemplos en C# para visualizar su impacto.
¿Qué es la Complejidad Algorítmica?
La complejidad algorítmica mide cuántos recursos (tiempo y memoria) necesita un algoritmo para ejecutarse en función del tamaño de la entrada. Un algoritmo eficiente es aquel que resuelve un problema rápidamente y sin consumir demasiada memoria.
Ejemplo en la vida real:
- Buscar un libro en una biblioteca desordenada (requiere más tiempo).
- Buscar un libro en una biblioteca organizada alfabéticamente (requiere menos tiempo).
En programación, el objetivo es diseñar algoritmos eficientes para optimizar el rendimiento del software.
¿Qué es la Notación Big O?
Big O Notation es una forma de expresar cómo crece el tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de los datos de entrada.
Se representa como:
- O(1) → Tiempo constante
- O(log n) → Tiempo logarítmico
- O(n) → Tiempo lineal
- O(n log n) → Tiempo logarítmico lineal
- O(n²) → Tiempo cuadrático
- O(2^n) → Tiempo exponencial
- O(n!) → Tiempo factorial
Ejemplo de cómo crece el tiempo de ejecución en diferentes complejidades:
| Tamaño de Entrada (n) | O(1) | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 30 | 100 |
| 100 | 1 | 6 | 100 | 600 | 10,000 |
| 1000 | 1 | 10 | 1000 | 10,000 | 1,000,000 |
Entre más grande es «n», más impacta la elección del algoritmo en el rendimiento.
Ejemplos de Complejidad en C#
O(1) – Complejidad Constante
No importa el tamaño de los datos, el tiempo de ejecución siempre es el mismo.
int ObtenerPrimerElemento(int[] numeros)
{
return numeros[0]; // Siempre toma la primera posición
}
O(n) – Complejidad Lineal
El tiempo de ejecución crece proporcionalmente al tamaño de los datos.
void ImprimirNumeros(int[] numeros)
{
foreach (var num in numeros)
{
Console.WriteLine(num); // Se ejecuta una vez por cada número
}
}
O(n²) – Complejidad Cuadrática
Se ejecutan múltiples ciclos anidados, aumentando el tiempo exponencialmente.
void ImprimirPares(int[] numeros)
{
for (int i = 0; i < numeros.Length; i++)
{
for (int j = 0; j < numeros.Length; j++)
{
Console.WriteLine(numeros[i] + ", " + numeros[j]); // Ejecuta todas las combinaciones
}
}
}
Caso de uso real
Los motores de búsqueda como Google aplican algoritmos eficientes para mostrar resultados en milisegundos. Un algoritmo ingenuo que revisara todas las páginas web de manera secuencial (O(n)) tardaría demasiado. En su lugar, usan algoritmos eficientes como árboles de búsqueda y estructuras hash (O(log n) o O(1)) para indexar y recuperar información rápidamente.
Ejemplo en C#: Algoritmo de búsqueda eficiente con Diccionario (O(1))
using System;
using System.Collections.Generic;
class BusquedaRapida
{
static void Main()
{
Dictionary<string, string> diccionario = new Dictionary<string, string>
{
{ "C#", "Lenguaje de programación de Microsoft" },
{ "Python", "Lenguaje de alto nivel y multipropósito" },
{ "Java", "Lenguaje usado en aplicaciones empresariales" }
};
Console.WriteLine("Ingrese una palabra clave:");
string clave = Console.ReadLine();
if (diccionario.ContainsKey(clave))
{
Console.WriteLine("Definición: " + diccionario[clave]);
}
else
{
Console.WriteLine("Palabra no encontrada.");
}
}
}
Aquí, la búsqueda en un diccionario (hash table) tiene una complejidad de O(1), ya que encuentra la clave en tiempo constante sin importar cuántos elementos haya.
Desafío práctico
Ejercicio: Implementa un programa en C# que permita buscar un número en un array usando dos métodos:
- Búsqueda Lineal (O(n)) → Recorrer el array uno por uno.
- Búsqueda Binaria (O(log n)) → Usar la estrategia de dividir y conquistar.
Resumen de la clase
- La complejidad algorítmica mide la eficiencia de un algoritmo en términos de tiempo y espacio.
- Big O Notation nos ayuda a clasificar algoritmos según su rendimiento.
- Se implementaron ejemplos en C# con O(1), O(n) y O(n²).
- Se presentó un caso de uso real aplicado a motores de búsqueda.
Próxima clase: Estructuras de Datos Lineales – Arrays y Listas en C#
En la siguiente clase aprenderemos sobre Arrays y Listas en C#, su estructura interna, ventajas, desventajas y cuándo utilizar cada una para optimizar el rendimiento de nuestras aplicaciones.O
