0 Daumen
1,2k 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. 

Viele Grüße

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.

 

von 228 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
1 Antwort
Gefragt 13 Okt 2014 von anna19
0 Daumen
1 Antwort
Gefragt 8 Okt 2014 von Gast
0 Daumen
2 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community