Tenha cuidado com as armadilhas da complexidade do tempo

Escreva aqui

Um bilibili vedio também mostra isso: [Bilibili Video][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] e acho que é um bom vedio, mas seu idioma é o chinês.

complexidade de tempo

• O que significa complexidade de tempo?

• A complexidade do tempo é uma medida de quanto tempo um algoritmo leva para ser executado em função do tamanho de sua entrada. É uma forma de descrever a eficiência de um algoritmo e é usada para comparar diferentes algoritmos e determinar qual deles é o mais eficiente.

• Como calcular a complexidade do tempo?

• Para calcular a complexidade do tempo, precisamos considerar o número de operações realizadas pelo algoritmo em função do tamanho da entrada. A maneira mais comum de medir o número de operações é contando o número de vezes que uma determinada operação é executada.

• Quais são algumas armadilhas comuns ao calcular a complexidade do tempo?

• 1. Não considerando o tamanho da entrada: Se considerarmos apenas o número de operações realizadas pelo algoritmo, podemos subestimar a complexidade do tempo. Por exemplo, se contarmos o número de vezes que um loop é executado, mas não levarmos em conta o tamanho da entrada, então a complexidade do tempo pode ser muito alta.
• 1. Não considerando a eficiência do algoritmo: Alguns algoritmos podem realizar muitas operações mesmo quando o tamanho da entrada é pequeno, o que pode levar a uma alta complexidade de tempo. Por exemplo, algoritmos de classificação como classificação por bolha e classificação por seleção têm complexidade de tempo quadrática, embora possam precisar apenas trocar dois elementos em uma pequena matriz.
• 1. Não considerando o pior cenário do algoritmo: alguns algoritmos têm um cenário de melhor caso, onde executam menos operações do que o pior cenário. Por exemplo, algoritmos de pesquisa como a pesquisa binária têm um cenário de melhor caso, onde encontram o elemento alvo em tempo logarítmico, mas têm um cenário de pior caso, onde precisam examinar todos os elementos da matriz.

Vamos ver alguns exemplos de complexidade de tempo

Aqui está uma pergunta:
Encontre o máximo de 10 números inteiros em uma lista.

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

Aqui está a função de teste:

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

Solução 1: usar heap

Aqui está a solução que usa o módulo heapq:

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

Ou escrevemos no modo 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)

Solução 2: use classificação

Aqui está a solução que usa a função sort:

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

Quase todo mundo sabe que a complexidade de tempo do heap é O(n log k), e a complexidade de tempo da função de classificação é O(n log n).

Parece que a primeira solução é melhor que a segunda. Mas isso não é verdade em python.

Veja o 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)}")

Eu executo em Python3.11 VScode, aqui está o resultado:

n não é grande

Usar heapq: 0,002430099993944168
HeapQ Python: 0,06343129999004304
Classificado: 9.280000813305378e-05
n = 910
Usar Heapq: 9.220000356435776e-05
HeapQ Python: 0,07715500006452203
Classificado: 9.360001422464848e-05
n = 920
Usar Heapq: 9.440002031624317e-05
HeapQ Python: 0,06573969998862594
Ordenado: 0,00012450001668184996
n = 930
Usar Heapq: 9.689992293715477e-05
HeapQ Python: 0,06760239996947348
Classificado: 9.66999214142561e-05
n = 940
Usar Heapq: 9.600003249943256e-05
HeapQ Python: 0,07372559991199523
Classificado: 9.680003859102726e-05
n = 950
Usar Heapq: 9.770004544407129e-05
HeapQ Python: 0,07306570000946522
Classificado: 0,00011979998089373112
n = 960
Usar Heapq: 9.980006143450737e-05
HeapQ Python: 0,0771204000338912
Classificado: 0,00022829999215900898
n = 970
Usar Heapq: 0,0001601999392732978
HeapQ Python: 0,07493270002305508
Classificado: 0,00010840001050382853
n = 980
Usar Heapq: 9.949994273483753e-05
HeapQ Python: 0,07698320003692061
Classificado: 0,00010300008580088615
n = 990
Usar Heapq: 9.979994501918554e-05
HeapQ Python: 0,0848745999392122
Classificado: 0,00012620002962648869

se n for grande?

n = 10.000
Usar Heapq: 0,003642000025138259
HeapQ Python: 9.698883199947886
Classificado: 0,00107999995816499
n = 11.000
Usar Heapq: 0,0014836000045761466
HeapQ Python: 10.537632800056599
Classificado: 0,0012236000038683414
n = 12.000
Usar Heapq: 0,001384599949233234
HeapQ Python: 12.328411899972707
Classificado: 0,0013226999435573816
n = 13.000
Usar Heapq: 0,0020017001079395413
HeapQ Python: 15.637207800056785
Classificado: 0,0015075999544933438
n = 14.000
Usar Heapq: 0,0017026999266818166
HeapQ Python: 17.298848500009626
Classificado: 0,0016967999981716275
n = 15.000
Usar Heapq: 0,0017773000290617347
HeapQ Python: 20.780625900020823
Classificado: 0,0017105999868363142

O que encontro e como melhorar

Quando n é grande, Sorted custa um pouco de tempo (às vezes até melhor do que usar heapq), mas Python Heapq custa muito tempo.

• Por que Sorted custa um pouco de tempo, mas Python Heapq custa muito tempo?
• Como sorted() é uma função incorporada em Python, você pode encontrar o documento oficial do python sobre ela.

A função embutida é mais rápida que heapq porque é escrita em C, que é uma linguagem compilada.

• Como melhorar?
• Você pode usar a função integrada sorted() em vez de heapq.sort() para melhorar o desempenho do seu código. A função sorted() é uma função integrada em Python, que é implementada em C e é, portanto, muito mais rápida que heapq.sort()

Conculsão

Quando estamos lidando com grandes dados, devemos usar a função integrada em vez de heapq.sort() para melhorar o desempenho do nosso código. Devemos ter cuidado com as armadilhas da complexidade do tempo ao lidar com grandes volumes de dados. Às vezes, as armadilhas da complexidade do tempo são inevitáveis, mas devemos tentar evitá-las tanto quanto possível.

Sobre mim

Olá, meu nome é Mengqinyuan. Eu sou um estudante. Adoro aprender coisas novas.
Você pode ver meu github: [Github de MengQinYuan][https://github.com/mengqinyuan]