1. Definición
Notación matemática que describe el límite superior del tiempo de ejecución o el uso de espacio de un algoritmo. Se denota como O(f(n)), donde f(n) es una función que representa el tiempo o espacio en función del tamaño de la entrada n.
Mas información visita: http://bigocheatsheet.com
2. Propósito
- Comparación de Algoritmos: Permite comparar diferentes algoritmos y elegir el más eficiente para un problema dado.
- Escalabilidad: Ayuda a predecir cómo se comportará un algoritmo cuando la cantidad de datos aumenta.
3. Análisis de Complejidad
- Peor Caso: Se refiere al escenario donde el algoritmo tarda más tiempo o usa más recursos. Big O generalmente se refiere a este caso.
- Mejor Caso y Caso Promedio: Aunque son importantes, se utilizan menos frecuentemente para la notación Big O.
4. Espacio vs. Tiempo
- Complejidad Temporal: Se refiere al tiempo que tarda un algoritmo en ejecutarse.
- Complejidad Espacial: Se refiere a la cantidad de memoria adicional que utiliza. Puede tener notaciones como O(1) (espacio constante) o O(n) (espacio lineal).
Ejemplo:
import timeit
import matplotlib.pyplot as plt
import cProfile
# O(1)
def constant_time_operation():
return 42
# O(log n)
def logarithmic_time_operation(n):
count = 0
while n > 1:
n //= 2
count += 1
return count
# O(n)
def linear_time_operation(n):
total = 0
for i in range(n):
total += i
return total
# O(n log n)
def linear_logarithmic_time_operation(n):
if n <= 1:
return n
else:
return linear_logarithmic_time_operation(n - 1) + n
# O(n^2)
def quadratic_time_operation(n):
total = 0
for i in range(n):
for j in range(n):
total += i + j
return total
# O(2^n)
def exponential_time_operation(n):
if n <= 1:
return 1
else:
return exponential_time_operation(n - 1) + exponential_time_operation(n - 1)
# O(n!)
def factorial_time_operation(n):
if n == 0:
return 1
else:
return n * factorial_time_operation(n - 1)
# Function to measure execution time using timeit
def measure_time(func, *args):
execution_time = timeit.timeit(lambda: func(*args), number=1000)
return execution_time
def plot_results(results):
functions, times = zip(*results)
colors = ['skyblue', 'orange', 'green', 'red', 'purple', 'brown', 'pink']
plt.figure(figsize=(14, 8))
plt.bar(functions, times, color=colors)
for i, v in enumerate(times):
plt.text(i, v + 0.5, f"{v:.6f}", ha='center',
va='bottom', rotation=0, color='black')
plt.xlabel('Function Complexity')
plt.ylabel('Average Time (s)')
plt.title('Execution Time of Different Algorithm Complexities')
plt.grid(axis='y', linestyle='--', linewidth=0.5, color='gray', alpha=0.5)
plt.tight_layout()
plt.show()
def main():
results = []
results.append(("O(1)", measure_time(constant_time_operation)))
results.append(("O(log n)", measure_time(logarithmic_time_operation, 10)))
results.append(("O(n)", measure_time(linear_time_operation, 10)))
results.append(("O(n log n)", measure_time(
linear_logarithmic_time_operation, 10)))
results.append(("O(n^2)", measure_time(quadratic_time_operation, 7)))
results.append(("O(2^n)", measure_time(exponential_time_operation, 7)))
results.append(("O(n!)", measure_time(factorial_time_operation, 112)))
plot_results(results)
if __name__ == '__main__':
cProfile.run("main()", sort="totime", filename="output_profile.prof")
Recordar que no solo basta con aplicar notación big o si bien este es el primer paso existe otras formas de optimizar en memoria ejemplo el uso de slots, cache, hilos, paralelismo, procesos etc.
Gracias por leer !!
Apóyame reaccionando e opinando.
Top comments (0)