Bienvenido al Curso

1

Algoritmos y Estructuras de Datos: Curso Básico

Introducción a los algoritmos

2

Cómo Funcionan las Computadoras y el Sistema Binario

3

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

4

Estructuras de Datos para Rutas Más Cortas en Mapas

5

Algoritmo de Dijkstra para encontrar la ruta más corta

6

Metodología para Resolver Algoritmos Paso a Paso

7

Variables y Tipos de Datos en Programación

8

Creación de Tipos de Datos Personalizados en C

9

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

10

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

11

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

12

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

13

Tipos Abstractos de Datos: Listas, Pilas y Colas

14

Clases y objetos

15

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

16

Implementación de Queues con Arrays en Visual Studio Code

17

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

18

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

19

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

Algoritmos de ordenamiento

20

Algoritmos de Ordenamiento: Conceptos y Aplicaciones Básicas

21

Funcionamiento del Algoritmo de Ordenamiento Burbuja

22

Implementación de Bubble Sort en C paso a paso

23

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

24

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

25

Algoritmos de Ordenamiento Descendente: Implementación Práctica

Recursividad

26

Recursividad en Programación: Entendiendo el Factorial

27

Factorial Recursivo en C: Implementación y Ejemplo

28

Inversión de cadenas con recursividad en Java

29

Recursividad en Python: Arte con Turtle y Funciones Recursivas

Divide and conquer y programación dinámica

30

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

31

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

32

Ordenamiento de Arrays con MergeSort en C

33

Algoritmos de Ordenamiento de Datos de Mayor a Menor

34

Algoritmo Quicksort en Python: Implementación y Funcionamiento

35

Ordenamiento Quick Sort en Python paso a paso

Algoritmos 'Greedy'

36

Algoritmos Voraces: Principios y Aplicaciones Prácticas

37

Implementación de Algoritmo Greedy para Cambio de Monedas

38

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

Grafos y árboles

39

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

40

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

¿Cómo comparar Algoritmos?

41

Comparación de Algoritmos: Complejidad y Ritmo de Crecimiento

¿Qué sigue?

42

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

Comparación de Algoritmos: Complejidad y Ritmo de Crecimiento

41/42
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:

  1. Constante (O(1)): Tiempo de ejecución fijo, independiente del tamaño de la entrada.
  2. Logarítmico (O(log n)): Comúnmente usado en búsqueda binaria de datos organizados.
  3. Lineal (O(n)): El sistema recorre todos los elementos una vez, como en recorridos simples de listas.
  4. Lineal logarítmico (O(n log n)): Típico en algoritmos de ordenamiento eficientes como Merge Sort.
  5. Cuadrático (O(n^2)) y Cúbico (O(n^3)): Implícitos en métodos que involucran ciclos o agrupaciones de datos complejas.
  6. 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?

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!

++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)

La solución ideal es que vamos a representar el algoritmo como una función que va a depender del tamaño de la entrada, esto va a permitir comparar los diferentes tipos de ejecución independiente del tiempo que consume la maquina en resolver el algoritmo del estilo de programación o el lenguaje que estemos usando.
Vamos a ver algunos materiales que nos van a ayudar a comparar estos algoritmos sin importar el sistema o lenguaje que estemos usando.
Debemos tener en cuenta como se va a medir esto para eso vamos a usar un concepto importante que se llama ANÁLISIS DEL RITMO DE CRECIMIENTO DE LOS ALGORITMOS.
Un ejemplo seria cuando vamos a comprar un carro o una bicicleta y debemos ir directamente a las entradas mas caras, no a las menores.
Ejemplo: en el caso de comprar coche o bicicleta, compraríamos el coche porque es mucho mas costoso, de eso se trata el ANÁLISIS DEL RITMO DE CRECIMIENTO DE LOS ALGORITMOS.
1 CONSTANT= Imagínate que tienes que agregar cada vez mas un elemento a un stack de información o una lista, y esa lista consiste en agregar un dato mas en cada operación. Esto seria un tiempo de ejecución de uno y seria constante.
LOGN LOGARITHMIC= imaginemos que tenemos un arreglo ordenado de una forma que nosotros especificamos y tenemos que buscar en ese arreglo un dato especifico, esto tiene una complejidad de tiempo de tipo logarítmico, esta operación se puede realizar en cualquier calculadora, en este caso seria el numero de información que vas a meter al logaritmo.
N LINEAR= en este caso tenemos un arreglo no ordenado donde los datos van a estar ordenados aleatoria mente, el tiempo es de n al numero que tienes el dato por ejemplo: va a empezar a buscar desde la posición cero hasta la posición n y n va a ser el tiempo de ejecución, otro ejemplo seria si empieza desde cero y necesitas hallar un dato en la posición 20, 20 va a ser el tiempo de ejecución.
NLOGN LINEAR LOGARITHMIC= es un tipo de crecimiento logaritmico lineal, por ejemplo tienes varias listas o varios arreglos y debes ordenarlas por nivel, entonces iria, N^2 QUADRATIC,
N^3 CUBIC, 2^N EXPONENCIAL.
N^2 QUADRATIC= estos algoritmos tienen un ritmo de crecimiento mucho mayor, cuando la entrada va creciendo esto se vuelve una curva de crecimiento acelerado.
N^3 CUBIC= imagínate la multiplicación de dos matrices, entonces la matriz se va volviendo mas grande.
2^N EXPONENCIAL= crecimiento exponencial, donde sera con base 2 a la n, entonces la potencia se incrementa, entonces el n crecería en este tipo de algoritmo.

No van a encontrar el material por que la clase pertenece a el curso anterior de Algoritmos, comparto el enlace por si gustan acceder.
.

Material del curso y clase :

https://static.platzi.com/media/public/uploads/Introduccion - Algoritmos con C_dc48ac3a-26a9-46f9-bd4c-a66e625c3c0b.pdf
.
Curso

https://platzi.com/cursos/algoritmos-2017/

soy yo o creo que este video es de otro curso o de una versión anterior del mismo? habla de cosas que no aplican al curso actual

Estaría genial ver algoritmos enfocados en Javascript. Más allá de que se pueden extrapolar los ejemplos que diste. Genial el curso.

Para que me quedara un poco más claro, realicé la siguiente imagen en una calculadora graficadora en línea. Cada línea representa el Ritmo de Crecimiento

Donde x representa el valor n(datos ingresados en el algoritmo), y y representa el crecimiento.

En el vídeo explican la complejidad algorítmica y su medición visto en un gráfico

me da la impresion de que este video, debería ir al principio, nombra clases que ya vimos al principio

Me percate de que esta clase forma parte del curso anterior y me puse a revisar. Hay cosas interesantes en el curso del 2017.
Les aconsejo que le den una mirada.
Curso de Algoritmos con C 2017

Les comparto otra aproximación al tema por si les ayuda a entenderlo mejor y no dejen de revisar Introducción a los algoritmos de Cormen 😃

interesante, pero el dice que nos vemos en la siguiente clase para concluir este tema y ya esta finalizando el curso. 😦

Este tema me parece que es muy interesante y al igual muchos considero que debe profundizar un poco más.

Aqui les dejo unos video con los que pueden aprender cómo analizar un algoritmo por el mejor y peor caso para calcular el ratio de crecimiento.

InsertionSort: https://www.youtube.com/watch?v=ZD9yICbSyBQ
MergeSort: https://www.youtube.com/watch?v=yKVjojlx8f4

En esta página se muestra la complejidad de algunos algoritmos y estructuras de datos en notacion Big O https://www.bigocheatsheet.com/

Hay una manera mucho mas sencilla de entender la comparacion de algoritmos y que significa cada tipo de ritmo de crecimiento. https://www.youtube.com/watch?v=O5LiA5ireA4

“ El análisis de eficiencia sera importante mas allá de los avances tecnológicos. ” - David Harel (2012)

Donde estan los materiales de apoyo?

Me surgio la duda… Escribir más lineas de codigo aumenta la cantidad de procesos y uso de recursos del ordenador? o eso no influye tanto?

Link a la descarga del libro Algorithms Notes for Professionals en pdf.
https://goalkicker.com/AlgorithmsBook/AlgorithmsNotesForProfessionals.pdf

Pienso que este tema debería ser mas profundo, constantemente como desarrolladores nos están preguntando por esto y es de vital importancia

saben cuando suben el curso de algoritmos avanzado?

Un poco de información que conseguí sobre evaluación de algoritmos:
http://verso.mat.uam.es/~pablo.angulo/doc/laboratorio/b2s2.html

El tema deberia ir al comienzo del curso, y leyendo en los comentarios veo que pertenece al curso de Algoritmos en C 2017
https://platzi.com/clases/algoritmos-2017/

Ritmos de crecimiento:

  • Constante (golden)
  • log n (best)
  • n (linear)
  • nlogn
  • n^2
  • n^3
  • 2^n
  • n^n (the worst)

Otra manera que podemos comparar, aunque no tan comun, es el uso de la memoria. Normalmente entre mas rapido es un algoritmo, mas memoria utiliza

vea ppues , cosas que una piensa que nada qeu ver …

El tiempo de ejecución y cantidad de lineas de código del algoritmo seleccionado. No son buenas métricas para escoger un algoritmo eficiente. La métrica correcta sería comparar los algoritmos dependiendo de la envergadura de entradas de datos.

Para tener referencias de la magnitud de datos del problema a resolver con la del algoritmo. Se puede utilizar la tabla de ratio de algoritmos.

Quiero profundizar en este tema, genial, aunque sea de otro curso, estuvo buena la clase, solucione dudas que tenía.

Hay un error en el video, intente los diferentes servidores y es lo mismo probablemene un bug, me gustaba mas la otra interfaz de usuario espero sea una prueba esta

  • El tiempo de ejecución no es una buena métrica cuando se quiere comparar algoritmos, ya que varia según el tipo de computadora que se use.
  • El número de instrucciones tampoco no es una buena opción, ya que depende del lenguaje que se use.
  • Una buena opción es por el tamaño de entrada.
  • El análisis del ritmo de crecimiento, esta dado por el mayor coste del algoritmo.

[Ratio de crecimiento][1,2]

El escalamiento de un cálculo es el dolor de cabeza de todo computer science.

Me parece genial que seas ingeniero mecatrónico en México, yo también soy ingeniero en mecatrónica y me siento muy identificado con la descripción que diste al inico, por cierto ¿qué es un mecatrónico sin saber microcontroladores? Saludos

El Ratio de crecimiento es igual que la complejidad?

El tiempo de ejecución y cantidad de lineas de código del algoritmo seleccionado. No son buenas métricas para escoger un algoritmo eficiente. La métrica correcta sería comparar los algoritmos dependiendo de la envergadura de entradas de datos.

Comparar algoritmos.
Ritmo de crecimiento

¿Saldrá un curso de algoritmos avanzado?

Era más fácil poner un bucle que genere 200 numeros aleatorios

Buen video y muy buenos aportes de la comunidad!