Informatiker Board | Druckvorschau: Algorithmus, der überprüft ob eine Summe existiert

Geschrieben von felixgraf am 02.05.2017 um 17:02:

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

Geschrieben von eulerscheZahl am 05.05.2017 um 19:30:

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.