Hallo,
was ist mit anstelle von Sortieren das algorithmische Problem „identifiziere die Input-Permutation“ zu analysieren. (Folie 4 gemeint?
Untere Schranke der asympt. Komplexität für paarw. Vergleich
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Untere Schranke der asympt. Komplexität für paarw. Vergleich
Das erste Problem ist mindestens so schwer, wie das zweite. Das heißt, wenn man für das zweite Problem \(\Omega(n\log n)\) beweist, dann ist das auch für das erste und eigentlich interessierende Problem bewiesen. Daher können wir das zweite anstelle des ersten Problems betrachten, was uns das Leben sehr viel einfacher macht.sqrt(2) hat geschrieben: was ist mit anstelle von Sortieren das algorithmische Problem „identifiziere die Input-Permutation“ zu analysieren. (Folie 4 gemeint?
KW
Re: Untere Schranke der asympt. Komplexität für paarw. Vergleich
Okay, dann bedeutet identifiziere die Input-Permutation lediglich das man weiß wie die Input-Permutation verändert werden muss damit man was sortiertes erhält?Prof. Karsten Weihe hat geschrieben:Das erste Problem ist mindestens so schwer, wie das zweite. Das heißt, wenn man für das zweite Problem \(\Omega(n\log n)\) beweist, dann ist das auch für das erste und eigentlich interessierende Problem bewiesen. Daher können wir das zweite anstelle des ersten Problems betrachten, was uns das Leben sehr viel einfacher macht.sqrt(2) hat geschrieben: was ist mit anstelle von Sortieren das algorithmische Problem „identifiziere die Input-Permutation“ zu analysieren. (Folie 4 gemeint?
Sortiere das algorithmische Problem wäre dann also man würde anfangen den Input zu sortieren und das sortierte Problem als Output zurückgeben?
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Untere Schranke der asympt. Komplexität für paarw. Vergleich
So kann man es auch ausdrücken.sqrt(2) hat geschrieben: Okay, dann bedeutet identifiziere die Input-Permutation lediglich das man weiß wie die Input-Permutation verändert werden muss damit man was sortiertes erhält?
So kann man es auch ausdrücken.sqrt(2) hat geschrieben: Sortiere das algorithmische Problem wäre dann also man würde anfangen den Input zu sortieren und das sortierte Problem als Output zurückgeben?

KW
Re: Untere Schranke der asympt. Komplexität für paarw. Vergleich
Prof. Karsten Weihe hat geschrieben:So kann man es auch ausdrücken.sqrt(2) hat geschrieben: Okay, dann bedeutet identifiziere die Input-Permutation lediglich das man weiß wie die Input-Permutation verändert werden muss damit man was sortiertes erhält?
So kann man es auch ausdrücken.sqrt(2) hat geschrieben: Sortiere das algorithmische Problem wäre dann also man würde anfangen den Input zu sortieren und das sortierte Problem als Output zurückgeben?![]()
Okay, vielen dank! (: