Algorithmus, der überprüft ob eine Summe existiert |
02.05.2017, 17:02 | Auf diesen Beitrag antworten » | |||||
felixgraf | 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:
|
|||||
|
||||||
05.05.2017, 19:30 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | 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. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |
|