De reeks van tribonacci wordt gevormd door te beginnen met de getallen
\[0, 0, 1\]Elk volgend getal in de reeks is de som van de vorige 3 getallen. Zo bekom je de reeks
\[0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927,...\]Hieronder vind je een recursief algoritme dat het n-de tribonacci getal uitrekent:
def tribonacci(n, hashmap={}):
if n in hashmap:
return hashmap[n]
if n < 2:
return 0
if n == 2:
return 1
hashmap[n] = tribonacci(n-3) + tribonacci(n-2) + tribonacci(n-1)
return hashmap[n]
Dit is een recursief algoritme, waarbij er een geziene techniek gebruikt werd om de functie te verbeteren. Kopieer onderstaand kader in het invulveld, waarbij je antwoord op de vragen over dit algoritme. Vervang telkens <jouw antwoord> door jouw antwoord.
# Vraag 1: Welke techniek werd hier gebruikt? Wees specifiek!
# Antwoord: <jouw antwoord>
# Vraag 2: Op welke manier/manieren verandert deze techniek het algoritme?
# Antwoord: <jouw antwoord>
# Vraag 3: Wat is de tijdscomplexiteit van het algoritme mét en zonder de techniek?
# Kies uit O(sqrt(n)), O(n), O(n²), O(n³), O(log(n)), O(n*log(n)), O(exp)
# Complexiteit met techniek: <jouw antwoord>
# Complexiteit zonder techniek: <jouw antwoord>