Big O Notation eines Moduls in einer integrierten Methode in Python verschachtelt

Question

Ich frage mich über eine Begründung für die Bestimmung der großen O-Werte hinter eingebauten Methoden in Python. In Anbetracht der folgenden Operation:

i_arr = ['1','2','5','3','4','5','5'] 

s_arr = sorted(set(i_arr)) 

Meine Begründung ist, dass diese sorted(set) = n^2 zwei verschachtelte Schleifen bedeutet.

Basierend auf Rat, den ich in die höheren Level-Module als Teil meiner ursprünglichen Funktion im Quellcode Python gegraben:

def sorted(lst): 
     l = list(lst) 
     l.sort() 
     return l 

def sort(self): 
     sortable_files = sorted(map(os.path.split, self.files)) 

def set(self): 
     if not self._value: 
      self._value = True 

      for fut in self._waiters: 
       if not fut.done(): 
        fut.set_result(True) 

Jetzt bin verwirrt ich wirklich :)

Answer 1

Oberkomplexitätsgrenze von Sortieralgorithmus ist im Allgemeinen O (n * log (n)), wie auf wikipedia zu sehen ist. Dann hängt es davon ab, wie lange es dauert, das Array zum Set zu konvertieren. Von dem Beispiel, das Sie gepostet haben, können wir sehen, dass die Liste iteriert wird und in jedem Schritt wird überprüft, ob der Wert bereits im Satz ist oder nicht. Nach this hat die Überprüfung der Existenz von Element in Menge konstante Komplexität, O (1), so hat die ganze Konstruktion von Menge Komplexität O (n) wegen der Iteration über alle Elemente. Aber angenommen, dass es implementiert wird, indem jedes Element einzeln hinzugefügt wird, müssen wir über eine Liste iterieren, um es in die Menge zu transformieren, was O (n) ist, und dann sortieren wir es, das ist O (n * log (n)), und das führt zu Gesamtkomplexität O (n * log (n) + n) = 0 (n * log (n)).

Update:

Mapping hat auch lineare Komplexität, weil sie ganze Reihe iteriert und bildet jedes Element, aber da lineare Funktion wächst langsamer als n * log (n), jede lineare Operation hier nicht das O nicht beeinflusst (n * log (n)), so bleibt die asymptotische Komplexität auch bei der Abbildung gleich.

Answer 2

(N logN) ist die untere Grenze für einige Sortieralgorithmen wie schnelle Sortierung, Heap-Sortierung, Merge-Sortierung. Sie sind generische Vergleichsbasierte Algorithmen. Im schlimmsten Fall kann es O (N * N) sein.

Wenn die Elemente numerisch sind, gibt es O (N) -Obergrenzenalgorithmen wie radix sort, zoring sort und bucket sort.

Für Ihren Fall wird die Standardart der Python-Bibliothek verwendet, die timsort. TimSort ist in hohem Grade Optimierungs mergesort, es ist stabil und schneller als alter mergesort. Es läuft im schlimmsten Fall auf O (N log N).

Answer 3

Darüber hinaus antwortet "generische Sortierung" Leistung; Wie Sie sorted() erwähnen, nehme ich an, dass Sie nach den großen O-Werten hinter dieser eingebauten Methode in Python fragen.

Nun, Python verwendet Timsort; und zitieren aus wikipedia:

Timsort ist ein hybrider stabiler Sortieralgorithmus, der aus Merge-Sort- und Insertion-Sort abgeleitet wurde und für die Ausführung vieler realer Daten entwickelt wurde.

Im schlimmsten Fall benötigt Timsort O (n log n) -Vergleiche, um ein Array von n Elementen zu sortieren. Im besten Fall, der auftritt, wenn die Eingabe bereits sortiert ist, läuft sie in linearer Zeit, was bedeutet, dass es sich um einen adaptiven Sortieralgorithmus handelt.