Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » Laufzeitanalyse Quicksort

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 <
000
19.06.2005, 20:09 Uhr
~Jetro223
Gast


Hallo an alle, wusste leider nicht in welches Forum ich das posten sollte, da es kein Algorithmen Forum gibt

...ich schreib morgen eine wunderschöne Klausur und muss wahrscheinlich Quicksort erklären und dazu eine Laufzeitanalyse machen. Ich weiss, das Quicksort im schlechtesten Fall eine "Laufzeit" von n^2 hat und im Mittel eine Laufzeit von

n * log n

Warum? Wie kommt man da drauf?

...im netz finde ich leider nur recht unverständliche Erklärungen. Hat jemand davon Ahnung und kann mir evtl. helfen?

Über eine Antwort würde ich mich sehr freuen!

Ciao
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
19.06.2005, 20:41 Uhr
Pler
Einer von Vielen
(Operator)


hier wird sowas ähnliches mit verschiedenen puffergrößen gemacht.
( Effizienz von E/A- Pperationen )
Das Ergenis ist eine Tabelle mit:
Puffergröße, UserCPU, SystemCPU, Zeit, Scheifenläufe

Vielleicht kannste das irgendwie gebrauchen


C++:
#include  <sys/times.h>
#include  <sys/stat.h>
#include  <fcntl.h>
#include  "eighdr.h"

#define MAX_PUFFER_GROESSE  1<<20

static void
zeit_ausgabe(long int puff_groesse,
             clock_t realzeit, struct tms *start_zeit, struct tms *ende_zeit,
             long int schleiflaeufe);

int
main(void)
{
   char         puffer[MAX_PUFFER_GROESSE];
   ssize_t      n;
   long int     i, j=0, puffer_groesse;
   struct tms   start_zeit, ende_zeit;
   clock_t      uhr_start, uhr_ende;

   /*------- Ueberschrift fuer Zeittabelle ausgeben ------------------*/
   fprintf(stderr, "+------------+------------+------------"
                   "+------------+------------+\n");
   fprintf(stderr, "| %-10s | %-10s | %-10s | %-10s | %-10s |\n",
                   "Puffer-", "UserCPU", "SystemCPU",
                   "Gebrauchte", "Schleifen-");
   fprintf(stderr, "| %10s | %10s | %10s | %10s | %10s |\n",
                   " groesse", " (Sek)", " (Sek)",
                   " Uhrzeit", " laeufe");
   fprintf(stderr, "+------------+------------+------------"
                   "+------------+------------+\n");

   /*-------- Mit verschiedenen Puffergroessen die gleiche Datei von stdin ----*/
   /*-------- auf stdout kopieren. (Puffergroesse nimmt in Zweierpotenzen zu) -*/
   while (j <= 20) {
      i = 0;
      puffer_groesse = 1<<j;

      if (lseek(STDIN_FILENO, 0L, SEEK_SET) == -1)   /* Schreib/Lesezeiger in     */
         fehler_meld(FATAL_SYS, "Fehler bei lseek"); /* stdin auf Dateianf. setzen*/

      if ( (uhr_start = times(&start_zeit)) == -1)  /* Stoppuhr einschalten */
         fehler_meld(FATAL_SYS, "Fehler bei times");

      while ( (n = read(STDIN_FILENO, puffer, puffer_groesse)) > 0) {
         if (write(STDOUT_FILENO, puffer, n) != n)
            fehler_meld(FATAL_SYS, "Fehler bei write");
         i++;
      }
      if (n < 0)
         fehler_meld(FATAL_SYS, "Fehler bei read");
      
      if ( (uhr_ende = times(&ende_zeit)) == -1)   /* Stoppuhr ausschalten */
         fehler_meld(FATAL_SYS, "Fehler bei times");

      zeit_ausgabe(puffer_groesse, uhr_ende-uhr_start, &start_zeit, &ende_zeit, i);
      j++;
   }
   fprintf(stderr, "+------------+------------+------------"
                   "+------------+------------+\n");
   exit(0);
}

static void
zeit_ausgabe(long int puff_groesse,
             clock_t realzeit, struct tms *start_zeit, struct tms *ende_zeit,
             long int schleiflaeufe)
{
   static long   ticks=0;
  
   if (ticks == 0)
      if ( (ticks = sysconf(_SC_CLK_TCK)) < 0)
         fehler_meld(FATAL_SYS, "Fehler bei sysconf");

   fprintf(stderr, "| %10ld | %10.2lf | %10.2lf | %10.2lf | %10ld |\n",
                   puff_groesse,
                   (ende_zeit->tms_utime - start_zeit->tms_utime) / (double)ticks,
                   (ende_zeit->tms_stime - start_zeit->tms_stime) / (double)ticks,
                   realzeit / (double)ticks, schleiflaeufe);
   return;
}


Aus: Linux/Unix- Systemprogrammierung
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 <     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: