matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenKomplexität & BerechenbarkeitKompl. v. Algor. berechnen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Komplexität & Berechenbarkeit" - Kompl. v. Algor. berechnen
Kompl. v. Algor. berechnen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kompl. v. Algor. berechnen: Rückfragen
Status: (Frage) beantwortet Status 
Datum: 09:32 Sa 23.08.2014
Autor: NefetsClaxon

Aufgabe
a) Komplexität von Insertionsort
b) Komplexität von


a) Der Algorithmus hat O(n²) - mir geht's jetzt darum, das nachzuvollziehen.

Dazu muss ich ja die Anzahl der Elementarereignisse zählen, richtig?
Da kenne ich:
- Wertzuweisung
- Vergleich
- arithmetische Operationen
- Rückgabe eines Wertes

Hier die Implementierung:

1:
2: public class InsertionSort {
3:
4: public static void main(String[] args) {
5: int[] p = { 5, 3, 2, 6, 5, 2, 7, 0 };
6:
7: int[] g = sort(p);
8: for (int ff : g)
9: System.out.println(ff);
10: }
11:
12: private static int[] sort(int[] p) {
13: for (int i = 1; i < p.length; i++) {
14: int j = i;
15: int t = p[j];
16: while (j > 0 && p[j - 1] > t) {
17: p[j] = p[j - 1]; 
18: j--;
19: }
20: p[j] = t;
21: }
22: return p;
23: }
24: }


Da zähle ich in der Methode sort:
1 Wertzuweisung (int = 0)
i arithmetische Operationen (i-mal i++)
i Wertzuweisung (int j = i)
i  Wertzuweisung (int t = p[j])
j Wertzuweisungen (p[j] = p[j - 1])
j arithmetische Operationen (j--)
i Wertzuweisungen p[j] = t
1 Rückgabe

D. h. ich habe 1 + 4*i + i*j*2 Wertzuweisungen
Und i*j arithmetische Operationen
Und 1 Rückgabe

Also (1 + 4i + ij2) + (ij) + 1 Elementarereignisse
= 2 + 4i + 3ij

Also ich komme da auf gar keinen grünen Zweig...

b) Angenommen ein Algorithmus hat die Formel: 5n-1

Gibt es eine Konstante [mm] c_0 [/mm] , sodass f(n) = 5n-1 < [mm] c_0 [/mm] * n, wobei n > [mm] n_0 [/mm] und [mm] n_0 [/mm] > 0

Lösung soll sein: c = 5, [mm] n_0 [/mm] = 1

Wie komme ich den auf die Werte? Ich meine klar, dass 5n größer ist als 5n-1, aber muss ich das nicht theoretisch ausrechnen, also die Ungleichung lösen?

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Kompl. v. Algor. berechnen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:01 Sa 23.08.2014
Autor: Event_Horizon

Hi!

Du musst eher betrachten, wie häufig die Befehle ausgeführt werden.

hier hast du eine schleife,  die über alle Elemente des anfangsarrays läuft.  Das heißt,  sie lauft n mal.
Innerhalb der Schleife wird eine zweite schleife aufgerufen, die uber alle elemente des Ergebnisarrays lauft, und schaut, wo das aktuelle Element eingefügt werden muß. Im schlimmsten Fall lauft auch diese Schleife n mal. Das Innere dieser Schleife benötigt nun eine Zeit t, und wird von der inneren Schleife n mal durchlaufen. Und das ganze wird von der
äußeren schleife ebenfalls n mal aufgerufen, daher dauert das ganze schlimmstenfalls t*n*n, also mit der Ordnung n ^2 .

jetzt läuft die innere schleife nicht immer n mal, weil das Ergebnisarray ja wächst und die schleife anfangs scheller fertig ist. Aber das sorgt nut dafür,  dass sich die insgesamt benötigte Zeit um einen konstanten Faktor verringert. Es ändert nix am [mm] n^2 [/mm] .

die meisten Befehle sind von der ordnung 1, du musst nur schleifen genauer betrachten. Und wenn du vorgefertigte befehle aus bibliotheken o.ä. verwendest, können die auch ne höhere Ordnung haben.

Bezug
                
Bezug
Kompl. v. Algor. berechnen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:17 Di 26.08.2014
Autor: NefetsClaxon

Okay, super! Danke für die Erklärung!

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]