No tienes acceso a esta clase

¬°Contin√ļa aprendiendo! √önete y comienza a potenciar tu carrera

Calculando la complejidad de algoritmos

8/11
Recursos

Aportes 6

Preguntas 2

Ordenar por:

¬ŅQuieres ver m√°s aportes, preguntas y respuestas de la comunidad?

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

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)
 
 

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

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.

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

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