Was ist die Zeit-Komplexität einer Liste, die Konvertierung?

Habe festgestellt, dass die Tabelle die Zeit, die Komplexität der set-Operationen auf der offiziellen python-website. Aber ich will gerade Fragen, was ist die Zeit, die Komplexität der Umwandlung von einer Liste zu einem Satz, zum Beispiel,

l = [1, 2, 3, 4, 5]
s = set(l)

Ich weiß, dass dies eigentlich eine hash-Tabelle, aber wie funktioniert es genau? Ist es O(n) dann?

  • Sie konnte das irgendwie testen... Nur Zeit für zunehmende n. (Ich weiß nicht, aber ich denke, es sollte sein, da die Einfügung in eine hash-Tabelle ist die meiste Zeit O(1).).
  • Danke, ich glaube, ich war nur zu faul, ich sollte mit dem timer-Modul
  • timeit, timer nicht
InformationsquelleAutor Xuechen Li | 2016-01-06
  1. 27

    Ja. Iteration über eine Liste O(n) und das hinzufügen jedes element der hash-set ist O(1), so ist der gesamte Betrieb ist O(n).

    • In den wirklich schlimmer Fall, wenn man eine hash-Kollision zu jeder Zeit einfügen in eine hash-Tabelle wäre O(n) und O(n^2) insgesamt aber zum Glück fast nie passiert.
    • Auch, wenn Sie sehr schlechte Speicherverwaltung oder hash-binning und eine sehr große Liste, wird deine Leistung nicht O(n).
    InformationsquelleAutor Mad Physicist
Schreibe einen Kommentar