Best-case Zeitkomplexität für die Auswahl zu Sortieren

Warum ist das best-case Zeitkomplexität für selection sort O(n^2), wenn es O(n) für die insertion sort und bubble-sort? Ihre Durchschnittliche Zeiten gleich sind. Ich verstehe nicht, warum die best-case die Zeiten sind anders. Würde schätzen etwas Hilfe.

InformationsquelleAutor user3740951 | 2017-04-08
  1. 6

    Für die Auswahl zu Sortieren, die Sie haben auf der Suche nach minimum und legen Sie es auf den ersten Platz in der ersten iteration. In der zweiten iteration, Sie Suche das minimum in den nicht sortierten Teil des Arrays und legen Sie es auf den zweiten Platz und so weiter...

    Du nur wissen, welches element das minimum nach Durchlaufen, bis das Ende der nicht sortierte Teil. Auch wenn das array sortiert ist(!) Sie haben zu Durchlaufen, bis das Ende. Dann wissen Sie sicher, dass Sie gefunden, das minimum um es an der richtigen Stelle (am Ende der bereits sortierten Teil)

    Also ersten iteration dauert n Schritte zu finden, die minimale.
    Die zweite iteration dauert n-1-Schritte zu finden, die minimale in der nicht-sortierten Teil
    ...
    Die Letzte iteration dauert 1 Schritt zu finden, die minimale in der nicht-sortierten Teil.

    Nach diesen Schritten, Sie haben ein sortiertes array (selbst wenn Sie sortiert vor). Auswahl Sortieren nicht überprüfen, ob das array bereits sortiert ist durch eine linear-time algorithm. Auswahl Sortieren immer wieder sucht das minimum. Das ist die Art und Weise, wie die Auswahl Sortieren funktioniert.

    Wenn Sie wiederholt suchen das minimum das es braucht n+(n-1)+...+1, so bekommt man (n(n+1))/2 = (n2+n)/2 ist O(n2)

    • Aber ist es nicht der gleiche Fall für bubble-sort und insertion sort. Wir werden n Iterationen, selbst wenn das array sortiert ist, richtig? Warum ist das best-case-Zeit O(n)?
    • Wie Sie schon erwähnten, bubble sort und insertion sort wird führe n Iterationen, wenn das array sortiert ist. Das ist weniger als n^2 Schritte für die Auswahl zu Sortieren, da müssen wir n Iterationen für jedes der Elemente.
    • Ok hab es. In insertion sort, in jeder iteration, wenn wir feststellen, dass das erste element, die wir vergleichen, ist kleiner als der Schlüssel, wir nicht vergleichen, nicht weiter. Also für ein sortiertes array, die Zeit ist O(n)
    InformationsquelleAutor gartenkralle
Schreibe einen Kommentar