Vaya, en un curso anterior no entendí como funcionaban esos algoritmo, pero ahora si lo s estoy entendiendo y son brillantes.
0:00/8:21
Calculando la complejidad de algoritmos
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:
(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)
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)
(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
Muy buen explicado, si no lo explica así hubiera seguido viviendo con que cada vez que vea dos iteradores anidados era mala idea.
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.
aunque ya se para que sirve big o, no consigo entender bien su aplicación.
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:
Gracias profe!
No he entendido bien este tema, para que nos ayuda o en que momento del desarrollo hay que hacer estos calculos?
Excelente explicación
Marcos Mesias
Vaya, en un curso anterior no entendí como funcionaban esos algoritmo, pero ahora si lo s estoy entendiendo y son brillantes.
Mi Chu
¡La profesora es Excelente explicando! 🥳
Walter De Jesús Medina Puy
Pablo Torres Pérez
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
Es correcto, lo mismo detecté y revisé los comentarios para confirmar si alguien más.
Nicolas Alpargatero
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
exactamente, por costumbre ver un for dentro de otro for era pensar automaticamente es complejidad cuadratica
Irving Juárez
William Rodriguez
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
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
aunque ya se para que sirve big o, no consigo entender bien su aplicación.
Miguel Angel Reyes Moreno
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
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
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)
Ing. Moisés Toro
Gracias profe!
Fabian Garcia Alcala
No he entendido bien este tema, para que nos ayuda o en que momento del desarrollo hay que hacer estos calculos?
Nicolas Alpargatero
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
Este analisis lo haces al momento de analisar el problema y elegir la mejor solucion en tema de recursos y tiempo.
Camilo Castañeda
Excelente explicación
Miguel Angel Reyes Moreno
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
¿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?
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)
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.