T3: Bsp 4&5: Vergleich der beiden Funktionen

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
jr29zyni
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2016 15:03

T3: Bsp 4&5: Vergleich der beiden Funktionen

Beitrag von jr29zyni » 31. Mai 2016 21:30

Hallo,
  • darf man beim Vergleich der Komplexität von symdiff1 und symdiff2 annehmen, dass a.length = b.length gilt? Sonst muss der Limes nämlich für mehrere Variablen gegen unendlich laufen und v.a. mit L'Hospital komme ich dann da nicht mehr weiter, weil man ja gegen verschiedene Variablen ableiten müsste (und wir L'Hospital nicht für mehrere Variablen hatten)...
  • Liege ich damit richtig, dass wir bei beiden Algorithmen keine genauen Schranken finden können? Und vergleicht man in diesem Fall die worst-cases / oberen Schranken?
LG

Stefanie
Neuling
Neuling
Beiträge: 9
Registriert: 23. Jul 2015 09:44

Re: T3: Bsp 4&5: Vergleich der beiden Funktionen

Beitrag von Stefanie » 1. Jun 2016 11:17

Hallo,
Bei dem Vergleich habe ich auch noch ein Problem. Ich habe beide Komplexitäten bestimmt, aber ich weiß nicht wie ich nun die Konstanten bestimmen kann.

Danke und LG

Julian Prommer
Moderator
Moderator
Beiträge: 167
Registriert: 17. Apr 2013 15:48

Re: T3: Bsp 4&5: Vergleich der beiden Funktionen

Beitrag von Julian Prommer » 1. Jun 2016 16:06

Konstanten brauchen nicht bestimmt zu werden.
Es genügt Konstanten als c1,c2, usw. in die Terme zu multiplizieren.

Die genauen Kosten, Gewichte oder wie man die Konstanten nun auch mag zu bestimmen ist eine äußerst schwierige Aufgabe. Üblicherweise werden solche Probleme in Vertiefungsveranstaltungen angegangen. Mit Hausmitteln kann man eigentlich nur Assemblerprogramme genau bestimmen, wo der Programmierer jeden Prozessorbefehl selbst schreibt und in Tabellen nachschlagbar ist wieviele Takzyklen ein Befehl braucht.

Man kann sich Werte für die Konstanten zu Übungszwecke ausdenken oder abschätzen um somit break-even Berechnungen oder Entscheidungen für oder gegen eine Implementierung eines Algorithmus ausrechnen zu können.
Im Testat werden Zahlenwerte für Konstanten gegeben.

Beantwortet das die Frage?
AuD Orga

Stefanie
Neuling
Neuling
Beiträge: 9
Registriert: 23. Jul 2015 09:44

Re: T3: Bsp 4&5: Vergleich der beiden Funktionen

Beitrag von Stefanie » 1. Jun 2016 18:53

Ja.

Vielen Dank für die schnelle Antwort.

jr29zyni
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2016 15:03

Re: T3: Bsp 4&5: Vergleich der beiden Funktionen

Beitrag von jr29zyni » 1. Jun 2016 20:07

Meine Fragen aber noch bitte :twisted:

Julian Prommer
Moderator
Moderator
Beiträge: 167
Registriert: 17. Apr 2013 15:48

Re: T3: Bsp 4&5: Vergleich der beiden Funktionen

Beitrag von Julian Prommer » 2. Jun 2016 10:04

a.length und b.length sind zunächst nicht gleich.

In diesem Fall kommt es darauf an was man haben will.


Als erstes möchte ich eine sichere Abschätzung haben, die auf keinen Fall überschritten wird.
Man ersetzt a.length und b.length jeweils durch n=max(a.length,b.length). Wie angedeutet konstruiert man damit einen worst-case.
Dann ist nur noch die Variable n übrig auf die man möglicherweise mehrfach L´Hopital anwenden kann.

Nun will ich eine genauere Abschätzung haben, das wird regelmäßig schwieriger.
Dann macht es keinen Sinn a.length und b.length durch irgendwas zu ersetzen. L´Hopital ist zunächst nur für eine Variable gedacht.
Der Ausweg ist partielles Ableiten, dass sollte grad in Mathe 2 Thema sein. Zur Not Wikipedia: https://de.wikipedia.org/wiki/Partielle_Ableitung
oder ganz kurz gesagt: nach allen Variablen ableiten, dabei entstehen Ableitungsmatrizen (Gradient, Hessematrix, usw.). Wichtig ist das die partiellen Ableitungen stetig differenzierbar sind. Dann kann man den L´Hopital nacheinander auf die verschiedenen Variablen anwenden und zwar so lange bis entweder Zähler oder Nenner konstant wird, also wie gehabt.

Ich hoffe, das war hilfreich...
AuD Orga

jr29zyni
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2016 15:03

Re: T3: Bsp 4&5: Vergleich der beiden Funktionen

Beitrag von jr29zyni » 5. Jun 2016 23:06

Ja, vielen Dank!

Nicca
Windoof-User
Windoof-User
Beiträge: 33
Registriert: 7. Jun 2016 13:35

Re: T3: Bsp 4&5: Vergleich der beiden Funktionen

Beitrag von Nicca » 7. Jun 2016 13:44

Hallo,

gibt es irgendwo eine Lösung zu dem Übungsblatt? Ich bin nicht sicher, ob ich für Beispiel 4 die richtige Lösung habe :(

kci
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 21. Apr 2016 20:54

Re: T3: Bsp 4&5: Vergleich der beiden Funktionen

Beitrag von kci » 8. Jun 2016 02:12

f=2*c1*m*n+c2 als Funktion, daraus folgt f ∈ Θ(nm)

Antworten

Zurück zu „AuD: Theoretische Aufgaben“