Algorithmus, der überprüft ob eine Summe existiert
Ich soll einen Algorithmus angeben, dessen Worst-Case Laufzeit 0(n log_2(n)) beträgt und folgendes können soll:
Für eine gegebene endliche Menge S Teilmenge von Q| mit |S|=n und eine Zahl x in Q| wird entschieden, ob es zwei Elemente a,b in S gibt, deren Summe x ergibt.
Folgendes habe ich, weiß aber nicht ob das richtig ist:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
nehme an die Menge S sein ein Array mit S(0, … , n)
for a = 0 to n do
for b = 0 to n do
if (a + b = x) then do
gebe wahr zurück
end if
end do
end do
gebe falsch zurück
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von felixgraf: 02.05.2017 17:05.
Du prüfst zwar, ob die Summe x ist, aber in Laufzeit O(n^2).
Lösung:
Sortieren (in O(n^* log(n)))
und dann 2 Indizes auf das erste und letzte Element im Array.
wenn die Summe kleiner als x ist, musst du den ersten Index nach hinten schieben, sonst den zweiten nach vorne.
