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

[sqrt(2)]

Hallo,

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

[Prof. Karsten Weihe]

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

[sqrt(2)]

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]

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.

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

[sqrt(2)]

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.

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! (: