CursosEmpresasBlogLiveConfPrecios

Calculando la complejidad de algoritmos

Clase 8 de 11 • Curso de Entrevistas Técnicas: Estructuras de Datos y Algoritmos Avanzados

Clase anteriorSiguiente clase

Contenido del curso

Introducción

  • 1
    ¿Qué son las estructuras de datos y algoritmos?

    ¿Qué son las estructuras de datos y algoritmos?

    02:19 min
  • 2
    ¿Por qué importan las estructuras de datos y algoritmos?

    ¿Por qué importan las estructuras de datos y algoritmos?

    01:43 min
  • 3
    ¿Qué estructuras de datos y algoritmos aprender?

    ¿Qué estructuras de datos y algoritmos aprender?

    01:54 min

Preparación para entrevistas

  • 4
    ¿Cómo es (comúnmente) una entrevista con problemas de programación?

    ¿Cómo es (comúnmente) una entrevista con problemas de programación?

    06:54 min
  • 5
    5 pasos para resolver problemas de programación durante entrevistas

    5 pasos para resolver problemas de programación durante entrevistas

    12:10 min
  • 6
    Tips para entrevistas: preparación y ejecución

    Tips para entrevistas: preparación y ejecución

    12:35 min
  • Quiz: presentación de entrevistas con algoritmos

Mide la eficiencia de tus algoritmos

  • 7
    Notación Big O

    Notación Big O

    05:18 min
  • 8
    Calculando la complejidad de algoritmos

    Calculando la complejidad de algoritmos

    Viendo ahora
  • Quiz: notación big o

Bonus

  • 9
    Recursos útiles para aprender algoritmos

    Recursos útiles para aprender algoritmos

    02:55 min
  • 10

    Estructuras de Datos y Algoritmos: Conceptos Clave y Aplicaciones

    08:02 min

Próximos pasos

  • 11
    Toma los Cursos Avanzados de Algoritmos

    Toma los Cursos Avanzados de Algoritmos

    00:39 min
  • Tomar el examen del curso
    • Marcos Mesias

      Marcos Mesias

      student•
      hace 3 años

      Vaya, en un curso anterior no entendí como funcionaban esos algoritmo, pero ahora si lo s estoy entendiendo y son brillantes.

        Mi Chu

        Mi Chu

        student•
        hace 3 años

        ¡La profesora es Excelente explicando! 🥳

      Walter De Jesús Medina Puy

      Walter De Jesús Medina Puy

      student•
      hace 3 años

      He realizado la implementación de la estructura de dato: Queue utilizando Python, la construí utilizando listas y una segunda versión utilizando arrays de la librería numpy para poder compararlos:    

      Codigo que implementa Queue utilizando listas de python:

      (el archivo lo nombre como queue_with_lists.py)    

      from bokeh.plotting import figure, output_file, show import random import time def de_queue(data, items): if(data['front'] == -1): print("Our queue is empty") else: print(f"The value {items[data['front']]} was removed") items.pop(data['front']) if len(items): data['rear'] -= 1 else: data['front'] = data['rear'] = -1 def en_queue(value, data, items, SIZE): if data['rear'] == SIZE - 1: print("Our Queue is full") else: if data['front'] == -1: data['front'] = 0 data['rear'] += 1 items.append(value) def run(SIZE): items = [] data = { 'front': -1, 'rear': -1 } numbers_to_insert = SIZE numbers = [random.randint(0, 100) for i in range(numbers_to_insert)] start = time.time() for number in numbers: en_queue(number, data, items, SIZE) end = time.time() elapsed_time = end - start return elapsed_time if __name__ == '__main__': output_file('simple_graphic.html') fig = figure() SIZE = 5 # limite de elementos para la cola times = [] init_number = 100000 final_number = 1000000 step = 100000 data_sets = range(init_number, final_number, step) # this is my X axis for data_set in data_sets: times.append(run(data_set)) fig.line(list(data_sets), times, line_width=2) show(fig) print(data_sets) print(times)

         

      Código donde implemento Queue utilizando arrays de librería numpy

         

      from bokeh.plotting import figure, output_file, show from queue_with_lists import en_queue, run import random import numpy as np import time def de_queue(data, items): if(data['front'] == -1): print("Our queue is empty") else: print(f"The value {items[data['front']]} was removed") indices = list(range(0,items.size - 1)) values = items[1:items.size] np.put(items, indices, values) if data['rear']: data['rear'] -= 1 else: data['front'] = data['rear'] = -1 def en_queue_arr(number, data, items, SIZE): if data['rear'] == SIZE - 1: print("Our Queue is full") else: if data['front'] == -1: data['front'] = 0 data['rear'] += 1 items[data['rear']] = number def np_arrays(SIZE): items = np.empty(SIZE) data = { 'front': -1, 'rear': -1 } numbers_to_insert = SIZE numbers = [random.randint(0, 100) for i in range(numbers_to_insert)] start = time.time() for number in numbers: en_queue_arr(number, data, items, SIZE) end = time.time() elapsed_time = end - start return elapsed_time if __name__ == '__main__': output_file('simple_graphic.html') fig = figure() SIZE = 5 # limite de elementos para la cola times = [] times_list = [] init_number = 100000 final_number = 10000000 step = 100000 data_sets = range(init_number, final_number, step) # this is my X axis for data_set in data_sets: times.append(np_arrays(data_set)) times_list.append(run(data_set)) fig = figure(title="Array vs Linked List - Queue", x_axis_label='Cantidad de elementos en cola', y_axis_label='Tiempo') fig.line(list(data_sets), times, legend_label="Arrays", color="blue", line_width=2) fig.line(list(data_sets), times_list, legend_label="Linked Lists", color="orange", line_width=2) show(fig)

         

      Gráfica con los resultados:

      (la comparación es al insertar a la Queue hasta 10 millones de datos)    

      Pablo Torres Pérez

      Pablo Torres Pérez

      student•
      hace 3 años

      Me parece que hay pequeños errores en el código de complejidad Logarítmica. (Corríjanme si me equivoco) 1.- Para la búsqueda binaria, la función debería recibir el parámetro target. 2.- Se debe utilizar a lista en lugar de nums.

      Quedando el código corregido como el siguiente:

      def busqueda_binaria(lista, target): apuntador_izquierdo = 0 apuntador_derecho = len(lista) - 1 while apuntador_izquierdo <= apuntador_derecho: mitad = (apuntador_izquierdo + apuntador_derecho) // 2 if lista[mitad] == target: return mitad elif lista[mitad] < target: apuntador_izquierdo = mitad + 1 else: apuntador_derecho = mitad - 1 return -1
        José Luis Puc Sarmiento

        José Luis Puc Sarmiento

        student•
        hace 3 meses

        Es correcto, lo mismo detecté y revisé los comentarios para confirmar si alguien más.

      Nicolas Alpargatero

      Nicolas Alpargatero

      student•
      hace 2 años

      Muy buen explicado, si no lo explica así hubiera seguido viviendo con que cada vez que vea dos iteradores anidados era mala idea.

        Xavier Flores

        Xavier Flores

        student•
        hace 2 años

        exactamente, por costumbre ver un for dentro de otro for era pensar automaticamente es complejidad cuadratica

      Irving Juárez

      Irving Juárez

      student•
      hace 3 años

      En el caso del ejemplo de la complejidad cuadratica (matriz), me parece que hubo un error en el código, ya que en el segundo for loop, siempre se hace con base en el primer elemento de la matriz matriz[0]

      Me parece que lo que realmente se quiere hacer en ese algoritmo es lo siguiente:

      def cuadratic(matrix): for i in range(len(matrix)): for j in range(len(matrix[i])): print(matrix[i][j])

      . Sin embargo, no se puede asegurar que es cuadrática. ya que las listas dentro de la matriz pueden variar. Por ejemplo, el output puede ser el siguiente:

      [ [0,0], [0,0,0,0], [0,0,0], [0], ]

      Claro que si sabemos de antemano que la longitud de las listas dentro de la matriz son iguales, podemos asumir que es cuadrática.

        William Rodriguez

        William Rodriguez

        student•
        hace 3 años

        En este caso no es un error. Por que el una matriz tanto tiene la misma cantidad de filas que de columnas por ende da lo mismo mirar len(matriz[0]) que cualquier otro len(matriz[3]) o incluso len(matriz) van a dar el mismo valor.

        Victor Hugo Vázquez Gómez

        Victor Hugo Vázquez Gómez

        student•
        hace 2 años

        Tienes razon en lo primero, pero si no conocemos los valores de cada fila de la matriz es O(n), no importa si en tu caso varia la longitud de cada fila, porque pueden existir casos donde si sean de la misma longitud. Ahora, si en todas las matrices que usas sabes que longitud va a tener cada una de las filas entonces ya es O(1).

      Frandel Corporan Rodríguez

      Frandel Corporan Rodríguez

      student•
      hace 2 años

      aunque ya se para que sirve big o, no consigo entender bien su aplicación.

        Miguel Angel Reyes Moreno

        Miguel Angel Reyes Moreno

        student•
        hace un año

        Piénsalo así: O(1) se tardará siempre el mismo tiempo en ejecutar tu programa, sin importar el tamaño de tu input o datos

        O(n) se tardará en tiempo la cantidad de datos que tengas, si tiene 1 dato, será (supongamos) 1 segundo. Si tienes 1000, serán 1000 segundos.

        O(n^2) tardará la cantidad de datos, pero al cuadrado. Si tienes 1 dato, tardará un segundo. Si tienes 5 datos tardará 25 segundos. Si tienes 1000 datos tardará 1 millón de segundos. Es un ejemplo burdo, pero la cosa es que podemos darnos cuenta de qué tan tardado y bien o mal optimizado está un código.

      Andres Silva Vega

      Andres Silva Vega

      student•
      hace 7 meses

      Puedo equivocarme. He tratado de hacer el análisis de la complejidad del algoritmo Merge Sort. Si alguien experto ve algo mal por favor desmiéntame:

        Andres Silva Vega

        Andres Silva Vega

        student•
        hace 7 meses

        Creo que la eficiencia de Merge Sort no es O(n log n) como menciono arriba sino O(2^n log n)) pues la función se llama a si misma 2 veces en cada iteración dando una eficiencia de O(2^n)

      Fabian Garcia Alcala

      Fabian Garcia Alcala

      student•
      hace 2 años

      No he entendido bien este tema, para que nos ayuda o en que momento del desarrollo hay que hacer estos calculos?

        Nicolas Alpargatero

        Nicolas Alpargatero

        student•
        hace 2 años

        Lo explica en el primer módulo, básicamente es porque hay muchas maneras de resolver un problema, y con Big O se puede decir cuál es el mejor por tiempo o espacio en memoria vs cantidad de datos, según lo que se requiera.

        Jhimy Michel

        Jhimy Michel

        student•
        hace 2 años

        Este analisis lo haces al momento de analisar el problema y elegir la mejor solucion en tema de recursos y tiempo.

      Camilo Castañeda

      Camilo Castañeda

      student•
      hace un año

      Excelente explicación

      Miguel Angel Reyes Moreno

      Miguel Angel Reyes Moreno

      student•
      hace un año

      Calculando la complejidad de los algoritmos

      Complejidad Lineal O(1)

      def complejidad_lineal(lista): suma = 0 multiplicacion = 1 for numero in range(len(lista)): suma += numero for numero in range(len(lista)): multiplicacion *= numero return suma, multiplicacion

      Complejidad Lineal O(n)

      def complejidad_lineal_2(lista): calculo = 0 for i in range(len(lista)): for j in range(1,5): calculo += (i*j) return calculo

      Complejidad Logarítmica O(log n)

      def busqueda_binaria(lista): apuntador_izquierdo = 0 apuntador_derecho = len(nums) - 1 while apuntador_izquierdo <= apuntador_derecho: mitad = (apuntador_izquierdo + apuntador_derecho) // 2 if nums[mitad] == target: return mitad elif nums[mitad] < target: apuntador_izquierdo = mitad + 1 else: apuntador_derecho = mitad - 1 return -1

      Complejidad Logarítmica (O n log n)

      Algoritmo de ordenamiento Merge Sort

      def merge_sort(arr): if len(arr) > 1: mid = len(arr)//2 izquierdo = arr[:mid] derecho = ar[mid:] merge_sort(izquierdo) merge_sort(derecho) i = j = k = 0 while i < len(izquierdo) and j < len(derecho): if izquierdo[i] = derecho[j]: arr[k] = izquierdo[i] i += 1 else: arr[k] = derecho[j] j += 1 k += 1 while i < len(izquierdo): arr[k] = izquierdo[i] i += 1 k += 1 while j < len(derecho): arr[k] = derecho[j] j += 1 k += 1

      Complejidad Cuadrática O(n²)

      def complejidad_cuadratica(matriz): for i in range(len(matriz)): for j in range(len(matriz[0])): if num[i][j] != 0: print(num[i][j])

      Complejidad Cuadrática

      def three_sum(numeros: List[int]) -> List[List[int]]: if len(numeros) < 3: return [] numeros.sort() resultado = set() for i in range(len(numeros)-2): if numeros[i] <= 0: if i === 0 or numeros[i-1] < numeros[i]: mapaParejas = {} for num in numeros[i+1:]: if num not in mapaParejas: mapaParejas[-numeros[i]-num] = 1 else: resultado.add((numeros[i], num, -numeros[i])) return [list(group) for group in resultado]

      Joselyn Reyna Contreras

      Joselyn Reyna Contreras

      student•
      hace 9 meses

      ¿Cuánto es un valor "chiquito" al hablar de la complejidad un ciclo anidado que se multiplica por un O(n)? En este caso dijo que O(5) se cancelaría por ser un valor pequeño, pero hasta qué punto deja de serlo?

    Escuelas

    • Desarrollo Web
      • Fundamentos del Desarrollo Web Profesional
      • Diseño y Desarrollo Frontend
      • Desarrollo Frontend con JavaScript
      • Desarrollo Frontend con Vue.js
      • Desarrollo Frontend con Angular
      • Desarrollo Frontend con React.js
      • Desarrollo Backend con Node.js
      • Desarrollo Backend con Python
      • Desarrollo Backend con Java
      • Desarrollo Backend con PHP
      • Desarrollo Backend con Ruby
      • Bases de Datos para Web
      • Seguridad Web & API
      • Testing Automatizado y QA para Web
      • Arquitecturas Web Modernas y Escalabilidad
      • DevOps y Cloud para Desarrolladores Web
    • English Academy
      • Inglés Básico A1
      • Inglés Básico A2
      • Inglés Intermedio B1
      • Inglés Intermedio Alto B2
      • Inglés Avanzado C1
      • Inglés para Propósitos Específicos
      • Inglés de Negocios
    • Marketing Digital
      • Fundamentos de Marketing Digital
      • Marketing de Contenidos y Redacción Persuasiva
      • SEO y Posicionamiento Web
      • Social Media Marketing y Community Management
      • Publicidad Digital y Paid Media
      • Analítica Digital y Optimización (CRO)
      • Estrategia de Marketing y Growth
      • Marketing de Marca y Comunicación Estratégica
      • Marketing para E-commerce
      • Marketing B2B
      • Inteligencia Artificial Aplicada al Marketing
      • Automatización del Marketing
      • Marca Personal y Marketing Freelance
      • Ventas y Experiencia del Cliente
      • Creación de Contenido para Redes Sociales
    • Inteligencia Artificial y Data Science
      • Fundamentos de Data Science y AI
      • Análisis y Visualización de Datos
      • Machine Learning y Deep Learning
      • Data Engineer
      • Inteligencia Artificial para la Productividad
      • Desarrollo de Aplicaciones con IA
      • AI Software Engineer
    • Ciberseguridad
      • Fundamentos de Ciberseguridad
      • Hacking Ético y Pentesting (Red Team)
      • Análisis de Malware e Ingeniería Forense
      • Seguridad Defensiva y Cumplimiento (Blue Team)
      • Ciberseguridad Estratégica
    • Liderazgo y Habilidades Blandas
      • Fundamentos de Habilidades Profesionales
      • Liderazgo y Gestión de Equipos
      • Comunicación Avanzada y Oratoria
      • Negociación y Resolución de Conflictos
      • Inteligencia Emocional y Autogestión
      • Productividad y Herramientas Digitales
      • Gestión de Proyectos y Metodologías Ágiles
      • Desarrollo de Carrera y Marca Personal
      • Diversidad, Inclusión y Entorno Laboral Saludable
      • Filosofía y Estrategia para Líderes
    • Diseño de Producto y UX
      • Fundamentos de Diseño UX/UI
      • Investigación de Usuarios (UX Research)
      • Arquitectura de Información y Usabilidad
      • Diseño de Interfaces y Prototipado (UI Design)
      • Sistemas de Diseño y DesignOps
      • Redacción UX (UX Writing)
      • Creatividad e Innovación en Diseño
      • Diseño Accesible e Inclusivo
      • Diseño Asistido por Inteligencia Artificial
      • Gestión de Producto y Liderazgo en Diseño
      • Diseño de Interacciones Emergentes (VUI/VR)
      • Desarrollo Web para Diseñadores
      • Diseño y Prototipado No-Code
    • Contenido Audiovisual
      • Fundamentos de Producción Audiovisual
      • Producción de Video para Plataformas Digitales
      • Producción de Audio y Podcast
      • Fotografía y Diseño Gráfico para Contenido Digital
      • Motion Graphics y Animación
      • Contenido Interactivo y Realidad Aumentada
      • Estrategia, Marketing y Monetización de Contenidos
    • Desarrollo Móvil
      • Fundamentos de Desarrollo Móvil
      • Desarrollo Nativo Android con Kotlin
      • Desarrollo Nativo iOS con Swift
      • Desarrollo Multiplataforma con React Native
      • Desarrollo Multiplataforma con Flutter
      • Arquitectura y Patrones de Diseño Móvil
      • Integración de APIs y Persistencia Móvil
      • Testing y Despliegue en Móvil
      • Diseño UX/UI para Móviles
    • Diseño Gráfico y Arte Digital
      • Fundamentos del Diseño Gráfico y Digital
      • Diseño de Identidad Visual y Branding
      • Ilustración Digital y Arte Conceptual
      • Diseño Editorial y de Empaques
      • Motion Graphics y Animación 3D
      • Diseño Gráfico Asistido por Inteligencia Artificial
      • Creatividad e Innovación en Diseño
    • Programación
      • Fundamentos de Programación e Ingeniería de Software
      • Herramientas de IA para el trabajo
      • Matemáticas para Programación
      • Programación con Python
      • Programación con JavaScript
      • Programación con TypeScript
      • Programación Orientada a Objetos con Java
      • Desarrollo con C# y .NET
      • Programación con PHP
      • Programación con Go y Rust
      • Programación Móvil con Swift y Kotlin
      • Programación con C y C++
      • Administración Básica de Servidores Linux
    • Negocios
      • Fundamentos de Negocios y Emprendimiento
      • Estrategia y Crecimiento Empresarial
      • Finanzas Personales y Corporativas
      • Inversión en Mercados Financieros
      • Ventas, CRM y Experiencia del Cliente
      • Operaciones, Logística y E-commerce
      • Gestión de Proyectos y Metodologías Ágiles
      • Aspectos Legales y Cumplimiento
      • Habilidades Directivas y Crecimiento Profesional
      • Diversidad e Inclusión en el Entorno Laboral
      • Herramientas Digitales y Automatización para Negocios
    • Blockchain y Web3
      • Fundamentos de Blockchain y Web3
      • Desarrollo de Smart Contracts y dApps
      • Finanzas Descentralizadas (DeFi)
      • NFTs y Economía de Creadores
      • Seguridad Blockchain
      • Ecosistemas Blockchain Alternativos (No-EVM)
      • Producto, Marketing y Legal en Web3
    • Recursos Humanos
      • Fundamentos y Cultura Organizacional en RRHH
      • Atracción y Selección de Talento
      • Cultura y Employee Experience
      • Gestión y Desarrollo de Talento
      • Desarrollo y Evaluación de Liderazgo
      • Diversidad, Equidad e Inclusión
      • AI y Automatización en Recursos Humanos
      • Tecnología y Automatización en RRHH
    • Finanzas e Inversiones
      • Fundamentos de Finanzas Personales y Corporativas
      • Análisis y Valoración Financiera
      • Inversión y Mercados de Capitales
      • Finanzas Descentralizadas (DeFi) y Criptoactivos
      • Finanzas y Estrategia para Startups
      • Inteligencia Artificial Aplicada a Finanzas
      • Domina Excel
      • Financial Analyst
      • Conseguir trabajo en Finanzas e Inversiones
    • Startups
      • Fundamentos y Validación de Ideas
      • Estrategia de Negocio y Product-Market Fit
      • Desarrollo de Producto y Operaciones Lean
      • Finanzas, Legal y Fundraising
      • Marketing, Ventas y Growth para Startups
      • Cultura, Talento y Liderazgo
      • Finanzas y Operaciones en Ecommerce
      • Startups Web3 y Blockchain
      • Startups con Impacto Social
      • Expansión y Ecosistema Startup
    • Cloud Computing y DevOps
      • Fundamentos de Cloud y DevOps
      • Administración de Servidores Linux
      • Contenerización y Orquestación
      • Infraestructura como Código (IaC) y CI/CD
      • Amazon Web Services
      • Microsoft Azure
      • Serverless y Observabilidad
      • Certificaciones Cloud (Preparación)
      • Plataforma Cloud GCP

    Platzi y comunidad

    • Platzi Business
    • Live Classes
    • Lanzamientos
    • Executive Program
    • Trabaja con nosotros
    • Podcast

    Recursos

    • Manual de Marca

    Soporte

    • Preguntas Frecuentes
    • Contáctanos

    Legal

    • Términos y Condiciones
    • Privacidad
    • Tyc promociones
    Reconocimientos
    Reconocimientos
    Logo reconocimientoTop 40 Mejores EdTech del mundo · 2024
    Logo reconocimientoPrimera Startup Latina admitida en YC · 2014
    Logo reconocimientoPrimera Startup EdTech · 2018
    Logo reconocimientoCEO Ganador Medalla por la Educación T4 & HP · 2024
    Logo reconocimientoCEO Mejor Emprendedor del año · 2024
    De LATAM conpara el mundo
    YoutubeInstagramLinkedInTikTokFacebookX (Twitter)Threads