kan iemand mij helpen met deze informatica/wiskunde vraag? het gaat vooral om vraag (13) A
bedankt!
hier de opgave:
(13) Hoe snel groeien functies? Hoe belangrijk is de snelheid van de computer voor
de uitvoering van een algoritme?
De rekentijd die nodig is voor een bepaald algoritme, als functie van de omvang van
het probleem N, gedraagt zich soms als een lineaire functie (0(N)), als een
logaritmische functie (0(log N)), als een kwadratische functie (0(N”2)), als een
exponentiële functie (0(2”N)): wat maakt dit in de praktijk uit?
Stel, je krijgt de beschikking over een modernere computer, die 1000 (of 1.000.000)
maal zo snel rekent als je vorige computer. Hiermee kun je, in dezelfde tijd, een groter
probleem uitrekenen dat met je oude computer; de vraag is nu: hoeveel groter kan dat
probleem zijn, voor algoritmen met het volgende gedrag van de rekentijd. Anders
geformuleerd: voor welke waarde x geldt dat f(x) = 1000 f(N)?
Voor f(N) = N is dit eenvoudig: x=1000, immers f(1000 * N) = 1000 * F(N)
«N) x waarvoor f(x) = 1000 * «N) x waarvoor f(x)10A6 *
«N)
log N
N 1000*N 1000000*N
N”2
NA3
2AN
a.) Maak de tabel compleet: bepaal genoemde x voor de andere functies; probeer eerst
een grove schatting te maken.
b.) Wat betekent dit voor Dijkstra’s algoritme? Hoeveel punten kun je extra in de graaf
opnemen als je over die snellere computer beschikt?
c.) Idem, voor het Traveling Salesman Problem? Met hoeveel steden kun je dit
uitbreiden?