0 Daumen
1,7k Aufrufe

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.

Avatar von

1 Antwort

0 Daumen

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.


Avatar von 287 k 🚀

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?

Stell deine Frage

Ähnliche Fragen

0 Daumen
2 Antworten
Gefragt 21 Apr 2022 von Tamtam
0 Daumen
1 Antwort
Gefragt 13 Okt 2014 von anna19
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community