Untere Schranke der asympt. Komplexität für paarw. Vergleich

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Untere Schranke der asympt. Komplexität für paarw. Vergleich

Beitrag von sqrt(2) » 12. Sep 2016 12:11

Hallo,

was ist mit anstelle von Sortieren das algorithmische Problem „identifiziere die Input-Permutation“ zu analysieren. (Folie 4 gemeint?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Untere Schranke der asympt. Komplexität für paarw. Vergleich

Beitrag von Prof. Karsten Weihe » 12. Sep 2016 14:55

sqrt(2) hat geschrieben: was ist mit anstelle von Sortieren das algorithmische Problem „identifiziere die Input-Permutation“ zu analysieren. (Folie 4 gemeint?
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.

KW

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Untere Schranke der asympt. Komplexität für paarw. Vergleich

Beitrag von sqrt(2) » 12. Sep 2016 20:06

Prof. Karsten Weihe hat geschrieben:
sqrt(2) hat geschrieben: was ist mit anstelle von Sortieren das algorithmische Problem „identifiziere die Input-Permutation“ zu analysieren. (Folie 4 gemeint?
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.
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?
Sortiere das algorithmische Problem wäre dann also man würde anfangen den Input zu sortieren und das sortierte Problem als Output zurückgeben?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Untere Schranke der asympt. Komplexität für paarw. Vergleich

Beitrag von Prof. Karsten Weihe » 12. Sep 2016 20:16

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?
So kann man es auch ausdrücken. :)

KW

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Untere Schranke der asympt. Komplexität für paarw. Vergleich

Beitrag von sqrt(2) » 13. Sep 2016 09:30

Prof. Karsten Weihe hat geschrieben:
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?
So kann man es auch ausdrücken. :)

Okay, vielen dank! (:

Antworten

Zurück zu „Archiv“