V
ausprobieren:
for k=|M| to 2*|M| //O(n) mal
bool test[k]={false,false,...} //O(n)
for i=1 to |M| //O(n) mal
r=M[i] mod k
if test[r]=true
goto warwohlnix
test[r]=true
next i
exit "juhu" k "gefunden"
:warwohlnix
next k
exit "nee so ein k ist nicht da"
macht O(n^2) zusammen.
vielleicht ist ja das das, was der prof haben will? von mit dem test-array von O(n^3) runterkommen auf O(n^2).
bin auf den trick gespannt, der das noch deutlich unterbietet. irgendwie glaub ich nicht dran.
schau mal http://www.onjava.com/pub/a/onjava/2001/01/25/hash_functions.html an. dem entnehme ich, daß es selten ist, daß k<=2*|M| ausreicht. im durchschnitt braucht er k=12*|M|.
