[FRAGE] - Beispiel 6
Results 1 to 5 of 5

Thread: Beispiel 6

  1. #1

    Title
    Principal
    Join Date
    Feb 2002
    Location
    Simmering
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Red face Beispiel 6

    "Welches dieser beiden Sortierverfahren ist im Durchschnitt (gemittelt über alle möglichen Eingabekombinationen) effizienter? Zeigen Sie dies ebenfalls, indem Sie für beide Algorithmen den Aufwand für den durchschnittlichen Fall in Theta-Notation angeben."

    Das steht nicht in yucrems Lösung... Sollen wir da etwa diese endlos lange Rumrechnerei wie er's in der Vorlesung gemacht hat für Insertion und Merge Sort machen? Ich glaub kaum, dass ich das schaffe...

  2. #2

    Title
    Dipl.Ing
    Join Date
    May 2002
    Posts
    1,074
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi,

    ich versteh ebenfalls nicht, was sie mit dieser Aufgabe meinen.

    Vielleicht kann irgendjemand helfen???

    :scheity

  3. #3

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Ich schaetze mal, dass einfach nur die Average Laufzeit dieser beiden Algorithmen gefragt sind (zumindest hoffe ich das, denn diese rumrechnerei wird sich jetzt wohl nicht mehr ausgehen ;-))

    Die Durchschnittliche Laufzeit von Insertion-Sort ist in \Theta(n^2) waerend Merge-Sort in \Theta(n log n) liegt, also ist Merge-Sort im Durchschnitt besser.

    Insertion-Sort liegt in \Theta(n^2) weil es passieren kann, dass jede Zahl mit jeder anderen verglichen werden muss (wenn die Folge absteigend sortiert ist).

    Merge-Sort teilt das Problem immer wieder in zwei kleinere Probleme auf, liegt also immer (Best = Average = Worst-Case) in \Theta(n log n).

    Btw. Ich freue mich ueber alle Hinweise und Korrekturen, aber bitte postet sie in den gleichen Thread wie die jeweilige Loesung.

    /edit 14.10.02:
    Theta ist dieser Kreis mit dem Strich in der Mitte.
    'O' heiszt einfach nur 'O' (siehe nachfolgender Post).
    Last edited by yrucrem; 15-10-2002 at 00:26.

  4. #4

    Title
    Dipl.Ing
    Join Date
    May 2002
    Posts
    1,074
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi, danke für die Erklärung nun habe ich nur mehr ein Problem, dass wahrscheinlich peinlich ist, aber es hilft ja nichts.

    Ich habe nirgends im Skriptum und in meiner Mitschrift etwas von Theta gelesen. Ist Theta etwa der Kreis mit dem Strich in der Mitte. Oder wie heisst das sonst.

    Falls ja, wie heisst eigentlich das grosse O. Nur "O"?

    thanks

  5. #5
    Judas42's Avatar
    Title
    Elite
    Join Date
    Jul 2002
    Location
    Wien
    Posts
    360
    Thanks
    0
    Thanked 1 Time in 1 Post
    Ich seh das O als Kürzel für Obere Schranke. Omega ist die untere Schranke, und bei Theta hat man beide drinnen. Da muß man aber bei oberer und unterer Schranke die gleiche Funktion nehmen, aber mit anderen Konstanten.

    das heißt, bei Theta beschreibst du das Verhalten relativ einfach mit EINER Funktion für oben und unten, bei O und Omega kannst du verschiedene Funktionen nehmen, und dich damit näher an den tatsächlichen Verlauf "herantasten"
    "The letters are Hex, of an ancient mode, but the language is that of Microsoft, which I shall not utter here."

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •