Tenga cuidado con los obstáculos de la complejidad del tiempo

Escribe aquí

Un vídeo bilibili también muestra esto: [Video Bilibili][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] y creo que es un buen vídeo, pero su idioma es el chino.

complejidad del tiempo

• ¿Qué significa complejidad temporal?

• La complejidad del tiempo es una medida de cuánto tiempo tarda un algoritmo en ejecutarse en función del tamaño de su entrada. Es una forma de describir la eficiencia de un algoritmo y se utiliza para comparar diferentes algoritmos y determinar cuál es el más eficiente.

• ¿Cómo calcular la complejidad del tiempo?

• Para calcular la complejidad del tiempo, debemos considerar el número de operaciones realizadas por el algoritmo en función del tamaño de la entrada. La forma más común de medir el número de operaciones es contando el número de veces que se realiza una operación en particular.

• ¿Cuáles son algunos errores comunes al calcular la complejidad del tiempo?

• 1. Sin considerar el tamaño de entrada: si solo consideramos la cantidad de operaciones realizadas por el algoritmo, podemos subestimar la complejidad del tiempo. Por ejemplo, si contamos el número de veces que se ejecuta un bucle, pero no tomamos en cuenta el tamaño de la entrada, entonces la complejidad del tiempo puede ser demasiado alta.
• 1. Sin considerar la eficiencia del algoritmo: algunos algoritmos pueden realizar muchas operaciones incluso cuando el tamaño de entrada es pequeño, lo que puede generar una gran complejidad temporal. Por ejemplo, los algoritmos de clasificación como la clasificación por burbujas y la clasificación por selección tienen una complejidad de tiempo cuadrática, aunque es posible que solo necesiten intercambiar dos elementos en una matriz pequeña.
• 1. Sin considerar el peor de los casos del algoritmo: algunos algoritmos tienen el mejor de los casos en el que realizan menos operaciones que el peor de los casos. Por ejemplo, los algoritmos de búsqueda como la búsqueda binaria tienen el mejor de los casos en el que encuentran el elemento de destino en tiempo logarítmico, pero tienen el peor de los casos en el que necesitan examinar todos los elementos de la matriz.

Veamos algunos ejemplos de complejidad del tiempo.

Aquí hay una pregunta:
Encuentra el máximo de 10 números enteros en una lista.

import random
ls = [random.randint(1, 100) for _ in range(n)]

Aquí está la función de prueba:

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

Solución 1: usar montón

Aquí está la solución que utiliza el módulo heapq:

def find_max_n(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

O lo escribimos en forma de Python:

def find_largest_n(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index   1
    right = 2 * index   2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)

Solución 2: usar clasificación

Aquí está la solución que utiliza la función de clasificación:

def find_max_n(ls, n):
    return sorted(ls, reverse=True)[:n]

Casi todo el mundo sabe que la complejidad temporal del montón es O (n log k), y la complejidad temporal de la función de clasificación es O (n log n).

Parece que la primera solución es mejor que la segunda. Pero no es cierto en Python.

Mira el código final:

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

def find_max_n_heapq(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

def find_max_n_python_heap(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index   1
    right = 2 * index   2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)


def find_max_n_sorted(ls, n):
    return sorted(ls, reverse=True)[:n]

# test
import random
for n in range(10, 10000, 100):
    ls = [random.randint(1, 100) for _ in range(n)]
    print(f"n = {n}")
    print(f"Use    Heapq: {benchmark(find_max_n_heapq, ls, n)}")
    print(f"Python Heapq: {benchmark(find_max_n_python_heap, ls, n)}")
    print(f"Sorted      : {benchmark(find_max_n_sorted, ls, n)}")

Lo ejecuto en Python3.11 VScode. Aquí está el resultado:

n no es grande

Usar Heapq: 0.002430099993944168
Montón de Python: 0.06343129999004304
Ordenado: 9.280000813305378e-05
norte = 910
Utilice Heapq: 9.220000356435776e-05
Montón de Python: 0.07715500006452203
Ordenado: 9.360001422464848e-05
norte = 920
Utilice Heapq: 9.440002031624317e-05
Montón de Python: 0.06573969998862594
Ordenado: 0.00012450001668184996
norte = 930
Utilice Heapq: 9.689992293715477e-05
Montón de Python: 0.06760239996947348
Ordenado : 9.66999214142561e-05
norte = 940
Utilice Heapq: 9.600003249943256e-05
Montón de Python: 0,07372559991199523
Ordenado: 9.680003859102726e-05
norte = 950
Utilice Heapq: 9.770004544407129e-05
Montón de Python: 0.07306570000946522
Ordenado: 0.00011979998089373112
norte = 960
Utilice Heapq: 9.980006143450737e-05
Montón de Python: 0.0771204000338912
Ordenado: 0.00022829999215900898
norte = 970
Utilice Heapq: 0.0001601999392732978
Montón de Python: 0.07493270002305508
Ordenado: 0.00010840001050382853
norte = 980
Utilice Heapq: 9.949994273483753e-05
Montón de Python: 0.07698320003692061
Ordenado: 0.00010300008580088615
norte = 990
Utilice Heapq: 9.979994501918554e-05
Montón de Python: 0.0848745999392122
Ordenado: 0.00012620002962648869

si n es grande?

n = 10000
Utilice Heapq: 0.003642000025138259
Montón de Python: 9.698883199947886
Ordenado: 0.00107999995816499
norte = 11000
Utilice Heapq: 0.0014836000045761466
Montón de Python: 10.537632800056599
Ordenado: 0.0012236000038683414
norte = 12000
Utilice Heapq: 0.001384599949233234
Montón de Python: 12.328411899972707
Ordenado: 0.0013226999435573816
norte = 13000
Usar Heapq: 0.0020017001079395413
Montón de Python: 15.637207800056785
Ordenado: 0.0015075999544933438
norte = 14000
Utilice Heapq: 0.0017026999266818166
Montón de Python: 17.298848500009626
Ordenado: 0.0016967999981716275
norte = 15000
Utilice Heapq: 0.0017773000290617347
Montón de Python: 20.780625900020823
Ordenado: 0.0017105999868363142

Qué encuentro y cómo mejorarlo

Cuando n es grande, Sorted cuesta un poco de tiempo (a veces incluso mejor que usar heapq), pero Python Heapq cuesta mucho tiempo.

• ¿Por qué Sorted cuesta poco tiempo, pero Python Heapq cuesta mucho tiempo?
• Debido a que sorted() es una función incorporada en Python, puedes encontrar el documento oficial de Python al respecto.

La función incorporada es más rápida que heapq porque está escrita en C, que es un lenguaje compilado.

• ¿Cómo mejorarlo?
• Puedes usar la función incorporada sorted() en lugar de heapq.sort() para mejorar el rendimiento de tu código. La función sorted() es una función incorporada en Python, que se implementa en C y, por lo tanto, es mucho más rápida que heapq.sort()

conculcion

Cuando tratamos con datos grandes, debemos usar la función incorporada en lugar de heapq.sort() para mejorar el rendimiento de nuestro código. Debemos tener cuidado con los problemas de complejidad del tiempo cuando se trata de grandes cantidades de datos. A veces, los problemas de complejidad del tiempo son inevitables, pero debemos intentar evitarlos tanto como sea posible.

Acerca de mí

Hola, soy mengqinyuan. Soy un estudiante. Me encanta aprender cosas nuevas.
Puedes ver mi github: [Github de MengQinYuan][https://github.com/mengqinyuan]