4. Shellsort - linear, quadratisch, logarithmisch oder asymptotisch?

Shellsort - linear, quadratisch, logarithmisch oder asymptotisch?

  • ?

    Hallo,

    für Shellsort ist angegeben average-case: O(n*log(n)²) und worst-case: O(n^1,25). Was ist dann Shellsort? Logarithmisch oder asymptotisch? Und was bezeichnet dieses o?

    Viele Dank

    0
  • F

    Es gibt keine vergleichbasierte Sortieralgorithmen mit logarithmischer / asymptotischer durchschnittlicher Laufzeitkomplexität. O\mathcal{O} ist das Landau-Symbol. O(g)\mathcal{O}(g) ist die Menge / Klasse (?) aller Funktionen, die nicht wesentlich schneller wachsen wie gg. Dabei sind nur die am schnellsten wachsenden Faktoren von Bedeutung:
    O(n2+5n)=O(n2+546543213)=O(n2+n)\mathcal{O}(n^2 + 5n) = \mathcal{O}(n^2 + 546543213) = \mathcal{O}(n^2 + n).

    O(n1.25)\mathcal{O}(n^{1.25}) ist polynomielle Laufzeitkomplexität.
    O(n⋅log(n)2)\mathcal{O}(n\cdot log(n)^2) ist eine super-lineare Laufzeitkomplexität.

    0
  • O

    O steht für die O-Notation aus der Komplexitätstheorie, siehe Landau-Symbole

    0
  • ?

    asfdlol schrieb:

    Es gibt keine vergleichbasierte Sortieralgorithmen mit logarithmischer / asymptotischer durchschnittlicher Laufzeitkomplexität. O\mathcal{O} ist das Landau-Symbol. O(g)\mathcal{O}(g) ist die Menge / Klasse (?) aller Funktionen, die nicht wesentlich schneller wachsen wie gg. Dabei sind nur die am schnellsten wachsenden Faktoren von Bedeutung:
    O(n2+5n)=O(n2+546543213)=O(n2+n)\mathcal{O}(n^2 + 5n) = \mathcal{O}(n^2 + 546543213) = \mathcal{O}(n^2 + n).

    O(n1.25)\mathcal{O}(n^{1.25}) ist polynomielle Laufzeitkomplexität.
    O(n⋅log(n)2)\mathcal{O}(n\cdot log(n)^2) ist eine super-lineare Laufzeitkomplexität.

    Ohje, muss ich das verstehen? 😕
    Also, ich habe hier eine Ankreuzaufgabe und die Frage lautet...
    Bei Shellsort ist der Sortieraufwand abhängig von der Anzahl der zu sortierenden Daten wie folgt:
    linear [ ]
    quadratisch [ ]
    logarithmisch [ ]
    asymptotisch [ ]

    0
  • I

    Gast66 schrieb:

    asfdlol schrieb:

    Es gibt keine vergleichbasierte Sortieralgorithmen mit logarithmischer / asymptotischer durchschnittlicher Laufzeitkomplexität. O\mathcal{O} ist das Landau-Symbol. O(g)\mathcal{O}(g) ist die Menge / Klasse (?) aller Funktionen, die nicht wesentlich schneller wachsen wie gg. Dabei sind nur die am schnellsten wachsenden Faktoren von Bedeutung:
    O(n2+5n)=O(n2+546543213)=O(n2+n)\mathcal{O}(n^2 + 5n) = \mathcal{O}(n^2 + 546543213) = \mathcal{O}(n^2 + n).

    O(n1.25)\mathcal{O}(n^{1.25}) ist polynomielle Laufzeitkomplexität.
    O(n⋅log(n)2)\mathcal{O}(n\cdot log(n)^2) ist eine super-lineare Laufzeitkomplexität.

    Ohje, muss ich das verstehen? 😕

    Ja.

    Gast66 schrieb:

    Also, ich habe hier eine Ankreuzaufgabe und die Frage lautet...
    Bei Shellsort ist der Sortieraufwand abhängig von der Anzahl der zu sortierenden Daten wie folgt:
    linear [ ]
    quadratisch [ ]
    logarithmisch [ ]

    Steht doch sogar im Wikipedia Artikel über Shellsort. Mit etwas Wissen über Sortieren mit Schlüsselvergleichen kannst du zwei onehin sofort ausschliessen.

    Gast66 schrieb:

    asymptotisch [ ]

    😕 Die Laufzeit wird asymptotisch gemessen - die konkrete Laufzeit asymptotisch gibt es nicht.

    0
  • F

    Ja, das hätte ich noch hinzufügen sollen. Asymptotisch selbst ist natürlich keine Komplexität. Gilt jedoch [latex]f \in \mathcal{O}(g)[/latex], so ist [latex]f[/latex] asymptotisch zu [latex]g[/latex], bzw. [latex]f \sim g[/latex].

    Edit: Siehe unten.

    0
  • I

    asfdlol schrieb:

    Gilt jedoch f∈O(g)f \in \mathcal{O}(g), so ist ff asymptotisch zu gg, bzw. f∼gf \sim g.

    Nein, betrachte f(n)=nf(n) = n und g(n)=n2g(n) = n^2. Dann gilt f∈O(g)f \in \mathcal{O}(g) aber ff wächst asymptotisch nicht gleich schnell wie gg.

    0
  • F

    Huch, ja, du hast recht. Ich hab' verpatzt, dass O\mathcal{O} auch alle langsameren Funktionen beinhaltet... Danke für den Hinweis.

    0

  • O(g)\mathcal{O}(g) ist die Menge / Klasse (?) aller Funktionen, die nicht wesentlich schneller wachsen wie gg.

    Nein. Die Menge wäre DTIME(g)DTIME(g).

    0
  • I

    Arcoth schrieb:

    O(g)\mathcal{O}(g) ist die Menge / Klasse (?) aller Funktionen, die nicht wesentlich schneller wachsen wie gg.

    Nein. [..]

    Ähm, doch 😕 Vielleicht sollte man wesentlich durch asymptotisch ersetzen aber ansonstent passt das.

    0
  • B

    Arcoth schrieb:

    Nein. Die Menge wäre DTIME(g)DTIME(g).

    Hä? Wie kann das auch nur entfernt stimmen, DTIME ist eine Menge von Entscheidungsproblemen, nicht von Funktionen.

    0
Anmelden zum Antworten