Vom Duplikat:
Titel: Informatik Knobelaufgabe: Algorithmus mit linearer Laufzeit
Stichworte: algorithmus,laufzeit,programm
Sehr geehrte Community,
ich habe mich in den letzten Tagen etwas mit Java beschäftigt und bin mittlerweile an dem Punkt angekommen, an dem ich mich mit Laufzeiten beschäftige. Auf einer Website habe ich dann leider eine Aufgabe gefunden, zu der ich keine Lösung weiß. Könnte mir evtl. jemand weiterhelfen oder mir zumindest einen kleinen Tipp geben?
Die Aufgabe:
Es existiert ein Feld A, welches aufsteigend sortiert ist. A enthält zudem reelle Zahlen n > 0. Des Weiteren sei eine reelle Zahl x gegeben. Geben sie einen Algorithmus mit der Laufzeit O(n) an, der bestimmt, ob es zwei Indizes 0 <= i < j < n gibt, sodass x = A{i} + A{j} gilt.
Ich freue mich über jede Art der Hilfe.
Mit freundlichen Grüßen