Fehler im Repetitorium?
Results 1 to 6 of 6
  1. #1

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts

    Fehler im Repetitorium?

    hi,

    mir is beim durschaun der mitschrift aufgefallen das dei laufzeit von quicksort laut georg kraml n²... im skript steht das dies ein fehler aus einem buch ist... in wirklichkeit (ohne beweis *G*) ist worstcase theta(nlogn).

    gruss laborg

  2. #2

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Worstcase = Feld ist aufsteigend sortiert

    Bei der Implementierung von Quicksort so wie sie im Skriptum ist, ist die Anzahl der Datenbewegungen Theta(n ) aber die Anzahl der Vergleiche ist Theta(n^2) (steht über dem Absatz mit dem Hinweis - Augen aufmachen )

  3. #3

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    hehe....k.

  4. #4
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    noch was:
    der insertion sorf müsste ja eigentlich Theta(n²) Schlüsselbewegungen haben, oder? (die größeren elemente rutschen ja alle ein stück nach rechts, wenn ein neues vom unsortierten teil reinsortiert wird)
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  5. #5
    #!/usr/bin/perl's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    291
    Thanks
    0
    Thanked 1 Time in 1 Post
    Original geschrieben von steve
    noch was:
    der insertion sorf müsste ja eigentlich Theta(n²) Schlüsselbewegungen haben, oder? (die größeren elemente rutschen ja alle ein stück nach rechts, wenn ein neues vom unsortierten teil reinsortiert wird)
    im worstcase schon ( absteigend sortiert ), im bestcase isa linear ( Folge bereits aufsteigend sortiert ).
    this is Unix land. In silent nights, you can hear Windows machines reboot...

  6. #6
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    naujo, ich bin einmal vom average ausgegangen, und der ist ja irgendwo dazwischen (wohl eher beim n², oder?)
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

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
  •