Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Komplexität von Algorithmen
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Komplexität von Algorithmen
 
Autor Nachricht
Wasserbaum
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 03.06.2008
Beiträge: 19

BeitragVerfasst am: 11 Feb 2009 - 14:07:14    Titel: Komplexität von Algorithmen

Hey,

gibt es eine Art Kochrezept für solche Aufgaben:

Zitat:

Die Rechenzeit eines Algorithmus beträgt auf einem AMD 3800+ (2 GHz)
unabhängig von der Anzahl der Elemente 3,6 s. Geben Sie die Komplexitätsklasse
des Algorithmus mit der O-Notation an.


? Ich habe bisher nicht den blassesten Schimmer, wie ich an diese Aufgabe herangehen sollte.

Auch eine solche
Zitat:

Ein Algorithmus benötigt für n Elemente 2n× logn + 5n + 4 Rechenschritte.
Geben Sie die Komplexitätsklasse dieses Algorithmus mit der O-Notation an.

Aufgabe liegt mir fern.

Das mit der oberen Schranke habe ich auc nicht so recht verstanden, auch wenn dies wohl recht einfach sein sollte, wie ich hörte.

Ich brauche den Stoff nur für eine Klausur und danach nie wieder, weshalb ich mich nicht "ransetze", sondern halt versuche, die Aufgaben einfach irgendwie zu lösen oder Punkte für Ansätze zu bekommen.

Kann mir jemand helfen?
Herr-Vorragend
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 13.12.2005
Beiträge: 101

BeitragVerfasst am: 11 Feb 2009 - 14:50:17    Titel:

Hi,

na das erste ist doch trivial, wenn die Ausführungszeit immer 2s ist, egal welche Daten man reinsteckt, dann sind wir in O(1), d.h. irgend eine Konstante gibt uns die maximale Laufzeit an.

Zum zweiten:

Code:
O(2n * logn + 5n + 4) = O(n*logn + n) = O(n*logn)


Einfach alle Faktoren, die nicht von n abhängen weglassen, Konstanten fallen komplett weg und "+n" fällt weg, weil n*logn immer stärker wächst als n.
O(a+b) ist ja das gleiche wie O(max(a,b)), uns interessiert ja nur das, was am stärksten wächst.

Gruß[/code]
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Komplexität von Algorithmen
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum