schneller algorithmus für ein problem

floppy

hallo,

ich muss morgen meine übung (Informatik I) abgeben und mir fehlt ein algorithmus:

Aufgabenstellung:
Geben Sie einen Algorithmus mit worst-case Laufzeit O(n log n) an, der folgendes leistet: Für eine gegebene endliche Menge S Teilmenge von Q(rationale Zahlen) und eine Zahl X Element von Q(rat. Zahlen) wird entschieden, ob es zwei Elemente a,b Element von S gibt, deren Summe x ergibt.

einen naiven Algorithmus für das Problem (mit quadratischer laufzeit) habe ich mir natürlich schon aus dem ärmel schütteln können:

#include <iostream>
using namespace std;

int main()
{
	double x=55, S[10]={2,4,4,6,8,12,43,64,65,76}, temp=0, summe=0;
	bool janein=0;

	for(int i=0; i < 10; i++)
	{
		temp=S[i];
		for(int j=i; j < 10; j++)
		{
			summe = temp+S[j];
			if(summe==x) janein=1;
		}
	}
	if (janein) cout << "jop" << endl;
	return 0;
}

aber er soll ja die Laufzeitfunktion T(n) = n log n haben...wir sollen das mit dem divide and conquer prinzip machen (also merge sort), dann gibts auch die gewünschte laufzeitfunktion...

void merge_sort(int *A, int p, int r)
{
	int q;
	if (p < r)
	{
		q = (p + r) / 2;
		merge_sort(A, p, q);
		merge_sort(A, q + 1, r);
		merge(A, p, q, r);
	}
}

merge_sort(...) ist klar, aber ich hab keine ahnung, was sich in merge() abspielen soll...

(log ist der zweierlogarithmus)

Erst Liste sortieren mit Mergesort: O(n*log(n))

Dann sei a das erste Listenelement und b := x-a
Teste ob b in der Liste ist mit Binärer Suche: O(log(n))

Wiederhole den Vorgang wobei du als a nacheinander, aufsteigend die Listenelemente nimmst.
Im schlechtesten Fall musst du diese Suche n mal wiederholen: O(n*log(n))

Ergibt zusammen O(n*log(n) + n*log(n)) = O(2*n*log(n)) = O(n*log(n))

(log ist der zweierlogarithmus)

Ist den Komplexitätstheoretikern völlig egal, weil sich die Logarithmen sowieso nur durch
einen konstanten Faktor unterscheiden

floppy

super! danke! du hast mir wirklich geholfen...habs genauso implementiert und es funktioniert prima... echt nett, dass du so schnell geantwortet hast.