Méfiez-vous des pièges liés à la complexité temporelle

Écrivez ici

Une vidéo bilibili montre également ceci : [Bilibili Video][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] et je pense que c'est une bonne vidéo, mais sa langue est le chinois.

complexité temporelle

• Que signifie la complexité temporelle ?

• La complexité temporelle est une mesure du temps nécessaire à l'exécution d'un algorithme en fonction de la taille de son entrée. C'est une façon de décrire l'efficacité d'un algorithme, et il est utilisé pour comparer différents algorithmes et déterminer lequel est le plus efficace.

• Comment calculer la complexité temporelle ?

• Pour calculer la complexité temporelle, nous devons considérer le nombre d'opérations effectuées par l'algorithme en fonction de la taille de l'entrée. La façon la plus courante de mesurer le nombre d'opérations consiste à compter le nombre de fois qu'une opération particulière est effectuée.

• Quels sont les pièges courants lors du calcul de la complexité temporelle ?

• 1. Ne pas tenir compte de la taille d'entrée : si l'on considère uniquement le nombre d'opérations effectuées par l'algorithme, nous pouvons sous-estimer la complexité temporelle. Par exemple, si nous comptons le nombre de fois qu'une boucle s'exécute, mais que nous ne prenons pas en compte la taille de l'entrée, alors la complexité temporelle peut être trop élevée.
• 1. Ne tient pas compte de l'efficacité de l'algorithme : certains algorithmes peuvent effectuer de nombreuses opérations même lorsque la taille d'entrée est petite, ce qui peut entraîner une complexité temporelle élevée. Par exemple, les algorithmes de tri tels que le tri à bulles et le tri par sélection ont une complexité temporelle quadratique, même s'ils n'ont besoin d'échanger que deux éléments dans un petit tableau.
• 1. Ne pas prendre en compte le pire des cas de l'algorithme : certains algorithmes ont un meilleur scénario dans lequel ils effectuent moins d'opérations que le pire des cas. Par exemple, les algorithmes de recherche tels que la recherche binaire ont un scénario optimal dans lequel ils trouvent l'élément cible en un temps logarithmique, mais ils ont un scénario pessimiste dans lequel ils doivent examiner tous les éléments du tableau.

Voyons quelques exemples de complexité temporelle

Voici une question :
Recherchez les 10 entiers maximum dans une liste.

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

Voici la fonction de test :

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

Solution 1 : utiliser le tas

Voici la solution qui utilise le module heapq :

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

Ou on l'écrit à la manière 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)

Solution 2 : utiliser le tri

Voici la solution qui utilise la fonction de tri :

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

Presque tout le monde sait que la complexité temporelle du tas est O(n log k) et la complexité temporelle de la fonction de tri est O(n log n).

Il semble que la première solution soit meilleure que la seconde. Mais ce n'est pas vrai en python.

Regardez le code 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)}")

Je l'exécute dans Python3.11 VScode, voici le résultat :

n n'est pas grand

Utiliser Heapq : 0,002430099993944168
Python Heapq : 0,06343129999004304
Trié : 9.280000813305378e-05
n = 910
Utilisez Heapq : 9.220000356435776e-05
Python Heapq : 0,07715500006452203
Trié : 9.360001422464848e-05
n = 920
Utilisez Heapq : 9.440002031624317e-05
Python Heapq : 0,06573969998862594
Trié : 0.00012450001668184996
n = 930
Utilisez Heapq : 9.689992293715477e-05
Python Heapq : 0,06760239996947348
Trié : 9.66999214142561e-05
n = 940
Utilisez Heapq : 9.600003249943256e-05
Python Heapq : 0,07372559991199523
Trié : 9.680003859102726e-05
n = 950
Utilisez Heapq : 9.770004544407129e-05
Python Heapq : 0,07306570000946522
Trié : 0.00011979998089373112
n = 960
Utilisez Heapq : 9.980006143450737e-05
Python Heapq : 0,0771204000338912
Trié : 0.00022829999215900898
n = 970
Utilisez Heapq : 0,0001601999392732978
Python Heapq : 0,07493270002305508
Trié : 0.00010840001050382853
n = 980
Utilisez Heapq : 9.949994273483753e-05
Python Heapq : 0,07698320003692061
Trié : 0.00010300008580088615
n = 990
Utilisez Heapq : 9.979994501918554e-05
Python Heapq : 0,0848745999392122
Trié : 0.00012620002962648869

si n est grand ?

n = 10000
Utilisez Heapq : 0.003642000025138259
Python Heapq : 9.698883199947886
Trié : 0.00107999995816499
n = 11 000
Utilisez Heapq : 0,0014836000045761466
Python Heapq : 10.537632800056599
Trié : 0.0012236000038683414
n = 12 000
Utilisez Heapq : 0,001384599949233234
Python Heapq : 12.328411899972707
Trié : 0.0013226999435573816
n = 13 000
Utilisez Heapq : 0,0020017001079395413
Python Heapq : 15.637207800056785
Trié : 0.0015075999544933438
n = 14 000
Utilisez Heapq : 0,0017026999266818166
Python Heapq : 17.298848500009626
Trié : 0.0016967999981716275
n = 15 000
Utilisez Heapq : 0,0017773000290617347
Python Heapq : 20.780625900020823
Trié : 0.0017105999868363142

Ce que je trouve et comment l'améliorer

Quand n est grand, Sorted coûte un peu de temps (parfois même mieux que d'utiliser heapq), mais Python Heapq coûte beaucoup de temps.

• Pourquoi Sorted coûte un peu de temps, mais Python Heapq coûte beaucoup de temps ?
• Parce que sorted() est une fonction intégrée en Python, vous pouvez trouver un document officiel de Python à ce sujet.

La fonction intégrée est plus rapide que heapq car elle est écrite en C, qui est un langage compilé.

• Comment l'améliorer ?
• Vous pouvez utiliser la fonction intégrée sorted() au lieu de heapq.sort() pour améliorer les performances de votre code. La fonction sorted() est une fonction intégrée à Python, implémentée en C et est donc beaucoup plus rapide que heapq.sort()

Conculsion

Lorsque nous traitons de données volumineuses, nous devrions utiliser la fonction intégrée au lieu de heapq.sort() pour améliorer les performances de notre code. Nous devons nous méfier des pièges liés à la complexité temporelle lorsque nous traitons de données volumineuses. Parfois, les pièges liés à la complexité temporelle sont inévitables, mais nous devons essayer de les éviter autant que possible.

Sur moi

Bonjour, je m'appelle Mengqinyuan. Je suis étudiant. J'aime apprendre de nouvelles choses.
Vous pouvez voir mon github : [Github de MengQinYuan][https://github.com/mengqinyuan]