Calculando la complejidad de algoritmos

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

Contenido del curso

Introducción

Preparación para entrevistas

Mide la eficiencia de tus algoritmos

Bonus

Próximos pasos

11
Toma los Cursos Avanzados de Algoritmos
00:39 min

Tomar examen

Walter De Jesús Medina Puy

student•

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)

Calculando la complejidad de algoritmos

Introducción

¿Qué son las estructuras de datos y algoritmos?

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

¿Qué estructuras de datos y algoritmos aprender?

Preparación para entrevistas

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

5 pasos para resolver problemas de programación durante entrevistas

Tips para entrevistas: preparación y ejecución

Mide la eficiencia de tus algoritmos

Notación Big O