Seien Sie vorsichtig bei den Fallstricken der Zeitkomplexität

Schreiben Sie hier

A bilibili vedio zeigt dies auch: [Bilibili Video][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] und ich denke, es ist ein gutes vedio, aber seine Sprache ist Chinesisch.

Zeitkomplexität

• Was bedeutet Zeitkomplexität?

• Zeitkomplexität ist ein Maß dafür, wie viel Zeit ein Algorithmus als Funktion der Größe seiner Eingabe benötigt, um auszuführen. Es ist eine Möglichkeit, die Effizienz eines Algorithmus zu beschreiben und wird verwendet, um verschiedene Algorithmen zu vergleichen und zu bestimmen, welcher am effizientesten ist.

• Wie berechnet man die Zeitkomplexität?

• Um die Zeitkomplexität zu berechnen, müssen wir die Anzahl der vom Algorithmus durchgeführten Operationen als Funktion der Größe der Eingabe berücksichtigen. Die gebräuchlichste Methode zum Messen der Anzahl von Vorgängen besteht darin, zu zählen, wie oft ein bestimmter Vorgang ausgeführt wird.

• Was sind einige häufige Fallstricke bei der Berechnung der Zeitkomplexität?

• 1. Ohne Berücksichtigung der Eingabegröße: Wenn wir nur die Anzahl der vom Algorithmus ausgeführten Operationen berücksichtigen, unterschätzen wir möglicherweise die zeitliche Komplexität. Wenn wir beispielsweise zählen, wie oft eine Schleife ausgeführt wird, aber die Größe der Eingabe nicht berücksichtigen, ist die zeitliche Komplexität möglicherweise zu hoch.
• 1. Ohne Berücksichtigung der Effizienz des Algorithmus: Einige Algorithmen führen möglicherweise viele Operationen aus, selbst wenn die Eingabegröße klein ist, was zu einer hohen Zeitkomplexität führen kann. Beispielsweise haben Sortieralgorithmen wie die Blasensortierung und die Auswahlsortierung eine quadratische Zeitkomplexität, auch wenn sie möglicherweise nur zwei Elemente in einem kleinen Array austauschen müssen.
• 1. Ohne Berücksichtigung des Worst-Case-Szenarios des Algorithmus: Einige Algorithmen haben ein Best-Case-Szenario, bei dem sie weniger Operationen ausführen als das Worst-Case-Szenario. Beispielsweise gibt es bei Suchalgorithmen wie der binären Suche ein Szenario im besten Fall, in dem sie das Zielelement in logarithmischer Zeit finden, im schlimmsten Fall jedoch das Szenario, in dem sie alle Elemente im Array untersuchen müssen.

Sehen wir uns einige Beispiele für Zeitkomplexität an

Hier ist eine Frage:
Finden Sie die maximal 10 Ganzzahlen in einer Liste.

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

Hier ist die Testfunktion:

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

Lösung 1: Heap verwenden

Hier ist die Lösung, die das Heapq-Modul verwendet:

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

Oder wir schreiben es auf Python-Art:

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)

Lösung 2: Sortieren verwenden

Hier ist die Lösung, die die Sortierfunktion verwendet:

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

Fast jeder weiß, dass die zeitliche Komplexität des Heaps O(n log k) und die zeitliche Komplexität der Sortierfunktion O(n log n) beträgt.

Es scheint, dass die erste Lösung besser ist als die zweite. Aber das stimmt nicht in Python.

Sehen Sie sich den endgültigen Code an:

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

Ich führe es in Python3.11 VScode aus. Hier ist das Ergebnis:

n ist nicht groß

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

wenn n groß ist?

n = 10000
Verwenden Sie Heapq: 0,003642000025138259
Python-Heapq: 9.698883199947886
Sortiert: 0,00107999995816499
n = 11000
Verwenden Sie Heapq: 0,0014836000045761466
Python-Heapq: 10.537632800056599
Sortiert: 0.0012236000038683414
n = 12000
Verwenden Sie Heapq: 0,001384599949233234
Python-Heapq: 12.328411899972707
Sortiert: 0.0013226999435573816
n = 13000
Verwenden Sie Heapq: 0,0020017001079395413
Python-Heapq: 15.637207800056785
Sortiert: 0,0015075999544933438
n = 14000
Verwenden Sie Heapq: 0,0017026999266818166
Python-Heapq: 17.298848500009626
Sortiert: 0,0016967999981716275
n = 15000
Verwenden Sie Heapq: 0,0017773000290617347
Python-Heapq: 20.780625900020823
Sortiert: 0,0017105999868363142

Was ich finde und wie ich es verbessern kann

Wenn n groß ist, kostet Sorted etwas Zeit (manchmal sogar besser als die Verwendung von Heapq), aber Python Heapq kostet viel Zeit.

• Warum kostet Sorted etwas Zeit, Python Heapq aber viel Zeit?
• Da sorted() eine integrierte Funktion in Python ist, finden Sie ein offizielles Python-Dokument dazu.

Die integrierte Funktion ist schneller als Heapq, da sie in C geschrieben ist, einer kompilierten Sprache.

• Wie kann man es verbessern?
• Sie können die integrierte Funktion sorted() anstelle von heapq.sort() verwenden, um die Leistung Ihres Codes zu verbessern. Die Funktion sorted() ist eine eingebaute Funktion in Python, die in C implementiert ist und daher viel schneller ist als heapq.sort()

Fazit

Wenn wir mit großen Datenmengen arbeiten, sollten wir die integrierte Funktion anstelle von heapq.sort() verwenden, um die Leistung unseres Codes zu verbessern. Beim Umgang mit großen Datenmengen müssen wir uns vor zeitlichen Komplexitätsproblemen in Acht nehmen. Manchmal sind Fallstricke bei der Zeitkomplexität unvermeidbar, aber wir sollten versuchen, sie so weit wie möglich zu vermeiden.

Über mich

Hallo, ich bin mengqinyuan. Ich bin ein Student. Ich liebe es, neue Dinge zu lernen.
Sie können meinen Github sehen: [MengQinYuans Github][https://github.com/mengqinyuan]