Cómo comparar algoritmos y ritmo de crecimiento

Curso Práctico de Estructuras de Datos y Algoritmos

Bienvenido al Curso

Algoritmos y Estructuras de Datos: Curso Básico

Introducción a los algoritmos

Cómo Funcionan las Computadoras y el Sistema Binario

Introducción a Lenguajes de Programación: Bajo y Alto Nivel

Estructuras de Datos para Rutas Más Cortas en Mapas

Algoritmo de Dijkstra para encontrar la ruta más corta

Metodología para Resolver Algoritmos Paso a Paso

Variables y Tipos de Datos en Programación

Creación de Tipos de Datos Personalizados en C

Configuración de Ubuntu en Windows 10 para C/C++

Implementación de User Defined Data Type en C: Estructuras paso a paso

Tipos de Datos Abstractos y Estructuras de Datos en Programación

Tipos Abstractos de Datos: Lista, Pila, Cola y Diccionario

Tipos Abstractos de Datos: Listas, Pilas y Colas

Clases y objetos

Colas y estructuras de datos: gestión de pedidos en restaurante

Implementación de Queues con Arrays en Visual Studio Code

Implementación de Abstract Data Type en C: Función enqueue

Implementación de la función dequeue en estructuras de datos en C

Implementación de Colas en C: Declaración y Uso de Funciones Básicas

Algoritmos de ordenamiento

Algoritmos de Ordenamiento: Conceptos y Aplicaciones Básicas

Funcionamiento del Algoritmo de Ordenamiento Burbuja

Implementación de Bubble Sort en C paso a paso

Implementación de Bubble Sort en C y función de impresión

Ordenamiento por Inserción en C: Algoritmo y Ejemplo Práctico

Algoritmos de Ordenamiento Descendente: Implementación Práctica

Recursividad

Recursividad en Programación: Entendiendo el Factorial

Factorial Recursivo en C: Implementación y Ejemplo

Inversión de cadenas con recursividad en Java

Recursividad en Python: Arte con Turtle y Funciones Recursivas

Divide and conquer y programación dinámica

Diseño y análisis de algoritmos: Divide y vencerás

Introducción a Programación Dinámica y Quicksort

Ordenamiento de Arrays con MergeSort en C

Algoritmos de Ordenamiento de Datos de Mayor a Menor

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Ordenamiento Quick Sort en Python paso a paso

Algoritmos 'Greedy'

Algoritmos Voraces: Principios y Aplicaciones Prácticas

Implementación de Algoritmo Greedy para Cambio de Monedas

Cambio de Monedas en C++: Implementación y Ejecución

Grafos y árboles

Introducción a Árboles y Grafos: Estructuras de Datos Básicas

Estructura de Datos: Árboles y sus Componentes Básicos

¿Cómo comparar Algoritmos?

Comparación de Algoritmos: Complejidad y Ritmo de Crecimiento

¿Qué sigue?

Resolución de Problemas Básicos con Algoritmos y Estructuras de Datos

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Si ya tienes una cuenta,

Recursos

¿Cómo comparar algoritmos de manera efectiva?

En el fascinante mundo de la Computación, comparar algoritmos es una habilidad esencial para cualquier desarrollador o científico. Sin embargo, es vital saber que existen métodos incorrectos y métodos adecuados para hacer estas comparaciones. No basta con medir el tiempo de ejecución, ya que esta métrica puede ser engañosa al depender del hardware del que disponemos. Implementaciones antiguas pueden ser más lentas en equipos recientes, lo que nos lleva a preguntarnos: ¿cuál es la mejor manera de comparar algoritmos?

¿Por qué el tiempo de ejecución no es una buena métrica?

El tiempo de ejecución varía significativamente entre diferentes sistemas y configuraciones de hardware. Por ejemplo, un algoritmo puede ejecutarse de manera completamente diferente en un procesador antiguo frente a uno reciente, o entre una computadora personal y un servidor en la nube. Además, el entorno de producción puede ser radicalmente distinto al de desarrollo, introduciendo más variables en la mezcla.

¿Por qué no usar el número de instrucciones del programa?

A simple vista, podría parecer que contar las líneas de código o instrucciones es una buena métrica para comparar algoritmos. No obstante, esta aproximación es errónea, ya que depende del lenguaje de programación escogido. Escribir en Java podría requerir menos líneas que en C, pero eso no indica que Java sea mejor en cuanto a eficiencia y desempeño.

¿Cuál es la solución ideal para comparar algoritmos?

La mejor solución es representar nuestro algoritmo como una función que depende del tamaño de la entrada. Al hacer esto, nos permite comparar el comportamiento del algoritmo de manera independiente a la plataforma o al lenguaje utilizado. Esto nos lleva a un concepto crucial: el ritmo de crecimiento.

¿Qué es el ritmo de crecimiento?

El ritmo de crecimiento, o rate of growth, aclara el comportamiento del algoritmo respecto al incremento de la entrada. Al igual que al comprar un coche miramos el costo total en lugar de desglosar cada gasto menor, en algoritmos nos centramos en el término de mayor peso en la función de complejidad.

Ejemplo básico

Supongamos que consideramos un polinomio como n^4 + 2n^2 + 100n + 500. Aquí el término dominante es n^4, que define el ritmo de crecimiento del algoritmo. Esto se traduce directamente a saber cómo se comportará el algoritmo con entradas cada vez más grandes.

¿Cómo medir el crecimiento con un ejemplo real?

Imagina que implementamos un algoritmo de ordenamiento sencillo en C, como el Insertion Sort. Al ejecutarlo, variamos la cantidad de datos ordenados para observar cómo cambia el número de movimientos. Con 10 elementos, el algoritmo es rápido. Sin embargo, con 200 elementos, vemos un aumento drástico, pasando de 23 movimientos a 7575. Esto se ilustra mediante la función de crecimiento que acompaña al algoritmo.

Código de implementación (C)

Veamos un segmento de código que ilustra este punto:

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Así, al probar con diferentes tamaños de entrada, observamos el efecto del ritmo de crecimiento en el rendimiento.

¿Cuáles son los tipos de crecimiento y sus implicaciones?

Entender los diferentes tipos de crecimiento nos ayuda a anticipar cómo un algoritmo manejará grandes volúmenes de datos:

Constante (O(1)): Tiempo de ejecución fijo, independiente del tamaño de la entrada.
Logarítmico (O(log n)): Comúnmente usado en búsqueda binaria de datos organizados.
Lineal (O(n)): El sistema recorre todos los elementos una vez, como en recorridos simples de listas.
Lineal logarítmico (O(n log n)): Típico en algoritmos de ordenamiento eficientes como Merge Sort.
Cuadrático (O(n^2)) y Cúbico (O(n^3)): Implícitos en métodos que involucran ciclos o agrupaciones de datos complejas.
Exponencial (O(2^n)): Aparente en algoritmos de complejidad combinatoria, como las Torres de Hanoi.

Embarcarte en el análisis de ritmos de crecimiento abrirá las puertas a un entendimiento más profundo de la eficiencia algorítmica. Con un enfoque cuidadoso y crítico, mejorarás tus habilidades y contribuirás a crear software más óptimo y escalable. ¡Sigue explorando y perfeccionando tus técnicas para enfrentar cualquier desafío algorítmico!

Aportes 38

Preguntas 2

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

_____pablo_

Profe Platzi

hace 6 años

Me parece genial que hablen acerca de estos temas, son vitales en el conocimiento de cualquier programador. Si quieren leer más a fondo sobre el tema, les comparto este post que escribí acerca de Complejidad Computacional, la disciplina encargada del análisis de algoritmos:

https://pablotrinidad.me/edd-2-complejidad-computacional/

Saludos y happy hacking!

Alejo Gschwind

hace 6 años

++Tipos de análisis de ejecución de un programa: ++

Análisis empírico: (poco recomendado)

• Requiere tener el código y ejecutarlo.
• La ejecución del programa se mide en unidades de tiempo.
• Se mide solo sobre una colección de entradas particulares.
• Lo que se mide depende de la computadora, el sistema operativo y el compilador, es decir depende de una implementación particular.

**Análisis teórico: **

• Análisis predictivo de eficiencia integrado al proceso de desarrollo de un programa.
• No depende de características de implementación.
• Establece cotas para el tiempo de ejecución en el “peor caso”, “mejor caso” y “caso promedio”.

Notación matemática en las que expresamos el tiempo de ejecución:

• Notación Big-Oh (mas usada)
• Notación Big-Omega
• Notación Zeta

Fuente: Introduction to Algorithms Ed. The MIT Press. (Capitulo 3 The Growth of Function)

Karen Paola Diaz Duarte