hat jemand eine Idee, wie ein Algorithmus aussehen könnte, der bei einem gegebenen Array aus n ganzen Zahlen und einer gegebenen Zahl c in Zeit O(n*log(n)) entscheidet, ob es zwei Zahlen a und b aus dem Array gibt, sodass a+b=c gilt?
Würde mich sehr über Tipps freuen.
wenn du was flottes zum Suchen hast vielleicht so
( in pascalähnlicher Notation)
For k:=1 to n begin x:=c-feld[k]
suche x in feld[k+1] bis feld[n]
end;
besser wohl wenn die äußere Schleife auch biem Finden
abbrechen kann.
Danke. Ich habe das so ähnlich gemacht. Erstmal das Array in O(nlog(n)) aufsteigend sortieren und danach etwa so wie du es beschrieben hast suchen.
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos