Algorithmus+Komplexität < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:34 Do 02.02.2006 | | Autor: | kuminitu |
| Aufgabe | Gegeben sei eine Menge M von n ganzen Zahlen sowie eine weitere ganze Zahl z. Entwerft einen Algorithmus, der in [mm] \theta(n [/mm] log n)-Zeit entscheidet, ob es in der Menge M zwei Zahlen gibt, deren Summe gerade z ist.
Begründet warum euer Algorithmus die geforderte Komplexität hat.
|
Hallo,
ich hab mir folgendes überlegt:
Man kann zu beginn auf jeden fall schon mal die
Zahlen aus der menge ausschließen, die größer als z sind.
und dann muss man doch die summe jedes möglichen paares
bilden und dann mit z vergleichen, oder?
aber da kommt eine größere Laufzeit als n*logn raus.
hat jemand zufällig eine bessere Idee für den Algorithmus?
MFG
kuminitu
PS:
falls nicht bekannt:
[mm] \theta(g) [/mm] := O(g) [mm] \cap (\Omega(g))
[/mm]
|
|
| |
|
Hallo kuminitu, und hallo Freunde gepflegter Algorithmik,
ein Vorschlag: Sortiere die Menge nach Groesse der Zahlen (Standard-Ordnung von [mm] \IZ),
[/mm]
dafuer brauchen wir [mm] O(n\log [/mm] (n)) Zeit. Dann nehmen wir zwei Variablen l und r, lassen
anfangs l= min(M) und r=max(M) sein, und lassen dann l und r aufeinander zulaufen:
Wir schauen, was l+r ist. Ist es kleiner als m, so ersetzen wir l durch das naechstgroessere Element von M, ist es groesser, so ersetzen wir r durch das nachstkleinere Element von M usw.
Dieser zweite Schritt braucht linear viele Schritte.
Man muss sich nun ueberlegen, dass dieses Verfahren korrekt arbeitet.
Bemerkung: dass der Algorithmus Laufzeit [mm] \Theta (n\log [/mm] n) hat, folgt daraus, dass
es zu jedem vergleichsorientierten Sortierverfahren Mengen gibt, fuer die das Verfahren
[mm] \Theta (n\log [/mm] n) Zeit braucht.
Interessanter ist es, fuer das PROBLEM SELBST eine untere Schranke von [mm] \Theta( n\log [/mm] n) zu zeigen, und dies kann man via Reduktion des Sortierproblems versuchen - hab mir keine Gedanken gemacht, ob diese untere Schranke ueberhaupt stimmt.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:42 Fr 03.02.2006 | | Autor: | kuminitu |
Hallo,
erstmal vielen dank für deine Antwort,
habe jetzt folgenden Algorithmus aufgestellt(java):
zuerst sortiere ich alle Zahlen(am besten mit Heapsort, um eine laufzeit von nlogn zu bekommen).die Implementierung spare ich mir jetzt.
(m und array werden der Methode übergeben)
int min = array[0];
int max = array[array.length-1]
int countermin =0; countermax = array.length-1;
while ( min+max != m){
if (min+max < m){
countermin++;
min = array[countermin];
}
else{
countermax--;
max = array[countermax]
}
(return max umd min wenn addition genau z
}
ist die methode richtig, bzw erfüllt sie auch die Laufzeit?
irgendwie habe ich es nicht kürzer hinbekommen.
MFG
kuminitu
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:08 Fr 03.02.2006 | | Autor: | Frank05 |
> habe jetzt folgenden Algorithmus aufgestellt(java):
>
> zuerst sortiere ich alle Zahlen(am besten mit Heapsort, um
> eine laufzeit von nlogn zu bekommen).die Implementierung
> spare ich mir jetzt.
// Klar, denn die Implementierung hats so richtig in sich 
java.util.Arrays.sort(array);
> (m und array werden der Methode übergeben)
> int min = array[0];
> int max = array[array.length-1]
> int countermin =0; countermax = array.length-1;
> while ( min+max != m){
> if (min+max < m){
> countermin++;
> min = array[countermin];
> }
> else{
> countermax--;
> max = array[countermax]
> }
> (return max umd min wenn addition genau z
> }
>
> ist die methode richtig, bzw erfüllt sie auch die
> Laufzeit?
> irgendwie habe ich es nicht kürzer hinbekommen.
Das Problem bei der Analyse der Laufzeit ist hier natürlich die while-Schleife. Und die ist ein echtes Problem, denn es muss ja nicht immer gelten, dass diese beiden Zahlen im Array existieren, die in der Summe m ergeben. Dann ist auch klar, dass min+max immer != m gilt und somit terminiert dein Algorithmus schonmal gar nicht.
Um eine Version davon zu entwickeln, über deren Laufzeit man leichter argumentieren kann, wäre also eine for-Schleife mit bekannter Schrittzahl vorteilhafter. Da du schlimmstenfalls alle Elemente des Arrays einmal für die Summe in Betracht ziehst genügt es hier O(array.length) oft die Indize anzupassen, womit du ungefähr auf so etwas kommst (Achtung: dieser Code hat noch nie einen Compiler aus der Nähe gesehen )
public static boolean isSumInArray(int [] array, int m) {
java.util.Arrays.sort(array);
int s,d, lo = 0, hi = array.length-1;
for (int i = 0; i < array.length-2; ++i) {
s = array[hi]+array[lo];
d = m-s;
if (d == 0) return true;
if (d < 0) hi--;
else lo++;
}
return false;
}
Hier ist die Laufzeit jetzt einfach abzulesen:
sort = [mm]\Theta(n*log n)[/mm]
dann [mm]O(n)[/mm] mal die Schleife, deren Rumpf in [mm]O(1)[/mm] ausgeführt wird, also bleibt die Komplexität bestimmt durch das Sortieren.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:27 So 05.02.2006 | | Autor: | kuminitu |
Hallo,
erstmal danke für die Hilfe, der Code funktioniert sehr gut,
erst aml ne kurze frage:
Welchen Algorithmus benutzt
java.util.Arrays.sort(array); ?
meine zweite frage ist so ähnlich wie das obige beispiel:
Ich habe wieder eine Menge M(wie oben), und will jetzt rausfinden ob eine neue Menge S eine Teilmenge von M ist.
habe mir erst aml folgendes überlegt:
public static boolean Teimenge(int[] M, int[] S)
{
boolean check = false;
for (int i = 0; i < S.length - 1; i++) {
for (int j = 0; j < M.length - 1; j++) {
if (S[i]==S[M])
check = true;
continue;
} // for2
if (check == false)
return false;
}//for1
return true;
}// part
Dabei sollte als Ziel der Algorithmus eine Laufzeit von $ [mm] \Theta (n\log [/mm] $ n)
haben, glaube jedoch nicht, das dies zu erreichen ist.
Mein problem ist jedoch, dass ich zwei for-schleifen benutze,
habs auch probiert wie beim ersten beispiel oben, bin aber auf keinen
guten Ansatz gekommen, bzw habe ich beide arrays sortiert und dann verglichen, aber as fordert ja auch ziemlich viel Aufwand.
Kann mir jemand bei diesem problem helfen?
MFG
Kuminitu
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:36 So 05.02.2006 | | Autor: | kuminitu |
ach ja,
und folgende bedingung soll gelten,
[mm] \summe_{x \varepsilon S}^{}x [/mm] = [mm] \summe_{x \varepsilon M \backslash S}^{}x
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:51 Mo 06.02.2006 | | Autor: | Frank05 |
> erst aml ne kurze frage:
> Welchen Algorithmus benutzt
> java.util.Arrays.sort(array); ?
Laut javadoc einen modifizierten Quicksort. Spielt aber denke ich nicht wirklich eine Rolle. Man muss sich dabei im Klaren sein, dass man diesen Aufruf jederzeit durch den Aufruf eines evtl. geeigneteren Sortierverfahrens ersetzen kann.
> meine zweite frage ist so ähnlich wie das obige beispiel:
>
> Ich habe wieder eine Menge M(wie oben), und will jetzt
> rausfinden ob eine neue Menge S eine Teilmenge von M ist.
Klingt sogar sehr ähnlich.
> habe mir erst aml folgendes überlegt:
>
> public static boolean Teimenge(int[] M, int[] S)
> {
> boolean check = false;
>
> for (int i = 0; i < S.length - 1; i++) {
> for (int j = 0; j < M.length - 1; j++) {
> if (S==S[M])
> check = true;
> continue;
> } // for2
> if (check == false)
> return false;
> }//for1
> return true;
> }// part
Hm.. irgendwie hats hier einen Teil rausgeschnitten.. naja jedenfalls hast du vergessen check für jeden Durchlauf der äußeren Schleife zurückzusetzen. Somit liefert die Method true gdw. der Schnitt von M und S nicht leer ist.
> Dabei sollte als Ziel der Algorithmus eine Laufzeit von
> [mm]\Theta (n\log[/mm] n)
> haben, glaube jedoch nicht, das dies zu erreichen ist.
Da sollte man bei Übungsaufgaben etwas vorsichtig sein. Meistens sind diese dann doch wider Erwarten richtig gestellt worden
> Mein problem ist jedoch, dass ich zwei for-schleifen
> benutze,
> habs auch probiert wie beim ersten beispiel oben, bin aber
> auf keinen
> guten Ansatz gekommen, bzw habe ich beide arrays sortiert
> und dann verglichen, aber as fordert ja auch ziemlich viel
> Aufwand.
Qualifiziere 'ziemlich viel Aufwand'? Auch [mm]\Theta (n log(n))[/mm] kann ziemlich viel Aufwand sein. Und du musst dir auch überlegen, welchen Vorteil du aus der Sortierung für deinen Algorithmus ziehen kannst. Einfach nur Sortieren und dann den Array so zu benutzen wie in deinem obigen Versuch bringt natürlich nichts.
(Ich gehe im Folgenden übrigens davon aus, dass die Arrays Mengen darstellen und somit gegeben ist, dass keine Elemente mehrfach darin vorkommen)
Also nehmen wir mal an, dass beide Arrays sortiert wurden. Wenn du nun das erste Element aus S nimmst, dann ist es somit das kleinste Element in S. Das vergleichen wir jetzt mit dem ersten Element in M.
Fall 1: die beiden Element sind gleich
Dann kannst du dieses Element in der Summe der S-Elemente dazurechnen und dir das zweite Element aus S ansehen. Aber nachdem wir jetzt schon wissen, dass M sortiert ist und das zweite Element aus S echt größer ist als das erste.. muss dann das erste Element in M überhaupt noch getestet werden ?
Fall 2: Element aus S < Element aus M
Nachdem das Element aus S das kleinste Element in S ist kann es kein Element in M geben, das mit dem ersten Element aus S übereinstimmt. Somit kann es sich nicht um eine Teilmenge handeln.
Fall 3: Element aus S > Element aus M
Da das kleinste Element in S größer ist als das kleinste Element in M kann das kleinste Element in M nicht in S vorkommen. Somit kannst du es zur Summe der [mm]M[/mm]\[mm]S\texttt{--Elemente}[/mm] zählen. Außerdem musst du es nie wieder bei einem Vergleich berücksichtigen, da es ja kein Element aus S geben kann, dass gleich diesem Element aus M ist. Da M sortiert ist und wir für das Element aus S ein Element mit größerem Wert brauchen genügt es sich das nächste Element anzusehen.
Jetzt musst du dir nur noch überlegen, wie man das auf alle Elemente von S verallgemeinert, und wie dann bei geschickter Implementierung die Laufzeit, bzw. das Programm, aussieht. Und bitte nicht einfach abhaken mit 'viel Aufwand', sondern mach dir immer die Mühe den Aufwand zumindest anhand der O-Notation abzuschätzen.
|
|
|
|
