Seite 1 von 1

T3: Bsp 4&5: Vergleich der beiden Funktionen

Verfasst: 31. Mai 2016 21:30
von jr29zyni
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

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

Verfasst: 1. Jun 2016 11:17
von Stefanie
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

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

Verfasst: 1. Jun 2016 16:06
von Julian Prommer
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?

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

Verfasst: 1. Jun 2016 18:53
von Stefanie
Ja.

Vielen Dank für die schnelle Antwort.

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

Verfasst: 1. Jun 2016 20:07
von jr29zyni
Meine Fragen aber noch bitte :twisted:

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

Verfasst: 2. Jun 2016 10:04
von Julian Prommer
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...

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

Verfasst: 5. Jun 2016 23:06
von jr29zyni
Ja, vielen Dank!

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

Verfasst: 7. Jun 2016 13:44
von Nicca
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 :(

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

Verfasst: 8. Jun 2016 02:12
von kci
f=2*c1*m*n+c2 als Funktion, daraus folgt f ∈ Θ(nm)