Algorithmus mit Laufzeit < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:51 So 27.04.2014 | | Autor: | Max80 |
| Aufgabe | <br>
Schreib einen Algorithmus mit worst case Laufzeit O(n Log n) der folgendes leistet: Für eine gegebene Menge S und Zahl x wird entschieden, ob es zwei Elemente in S gibt, deren Summe x ergibt. S und x sind rationale Zahlen. |
<br>
Hallo zusammen,
also der Algorithmus selbst ist ja eigentlich klar finde ich: Es soll geguckt werden, ob die dem Algorithmus übergebene Zahl die Summe von zwei Zahlen in S entspricht.
D.h. ich nehme die erste Zahl, addiere die Zweite hinzu. Passt es? Nein? Dann die erste und die dritte. Passt? usw.
Problem ist die vorgegebene Laufzeit. Wie kann ich jetzt den Algorithmus genau so entwickeln, dass er O(n*Log(n)) entspricht wie oben angegeben? Habt ihr da einen Tipp was ich machen kann?
Danke!!
Gruß
Max
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:46 Mo 28.04.2014 | | Autor: | Teufel |
Hi!
[mm] $n\log(n)$-Laufzeiten [/mm] riechen oft nach Sortieren. Also sortiere deine Zahlen der Größe nach und beginne dann mit der kleinsten Zahl [mm] $s_1\in [/mm] S$. Wenn [mm] $s_1+s_i=x$ [/mm] gelten soll, müsstest du nun nach [mm] $s_i=x-s_1$ [/mm] suchen. Wie schnell geht das? Und wie geht der Algorithmus dann weiter? Und hat er schon die geforderte Laufzeit?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:28 Di 29.04.2014 | | Autor: | Max80 |
<br>
Hi!
Danke für die Hilfe. Muss es denn immer S1 sein? Was wenn x z.B. 5 ist und die Menge enthält {1,2,3}, dann wäre S1 = 1 und damit käme ich aber nicht auf x.
Also muss ich alle durchlaufen (S1 + alle anderen) und wenn das nichts hilft, S2+alle anderen und so weiter, oder?
Ob das nun aber der Laufzeit entspricht oder nicht? Echt keine Ahnung. :(
Gruß
Max
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:06 Di 29.04.2014 | | Autor: | Teufel |
Hi!
Ja, wenn sich $x$ nicht so schreiben lässt, läuft der Algorithmus trotzdem bis zum Ende durch, findet aber eben nichts. Aber nehmen wir mal ein Positivbeispiel.
[mm] $S=\{4,2,6,7,9,1,1\}, [/mm] x=11$. Wir sortieren $S$ zuerst (wie lange dauert das bei $n$ Elementen?) und erhalten [mm] $S=\{1,1,2,4,6,7,9\}$.
[/mm]
Nun nehmen wir uns das erste (linkeste) Element, [mm] s_1=1. [/mm] Nun suchen wir ein [mm] $s_i=x-s_1=10$ [/mm] (damit [mm] $s_1+s_i=x$ [/mm] gilt). Das machen wir mit Binärsuche auf allen Elementen rechts von [mm] s_1. [/mm] Wie lange dauert diese Suche? Der Algorithmus wird nichts finden, also geht es mit [mm] s_2=1 [/mm] weiter. Binärsuche nach 10 auf allen Elementen rechts von [mm] s_2: [/mm] Er findet wieder nichts (klar).
Dann [mm] s_3=2. [/mm] Binärsuche nach [mm] x-s_3=9. [/mm] Der Algorithmus findet die 9 und kann [mm] s_3=2 [/mm] und [mm] x-s_3=9 [/mm] ausgeben.
Nun überlege noch, wie lange alle diese Schritte immer brauchen.
|
|
|
|
