Complexiteit

• neem twee getalen in een rij, bv. “0” en “1”. → `[0, 1]`
• maak het volgende element aan als de som van de vorige twee. Bv. “0 + 1 = 1”. → `[0, 1, 1]`
• herhaal de vorige stap → `[0, 1, 1, 2, 3, 5, …]`

Dit is de Rij van Fibonacci.

Oefening: zet die rij in je hoofd voort!

Wat doe jij als je die rij in je hoofd berekend?

• “Werkgeheugen”: vorige twee getalen onthouden.
• “Processor”: je weet hoe je de som vormt.

Wat komt er bij als je de getalen op papier schrijft?

• “Harde schrijf”: uitbesteding van je werkgeheugen, maar trager.

Een computer heeft dezelfde componenten:

• Processor (CPU)
• Werkgeheugen (RAM)
• Harde schrijf (HDD)

(doordenker: wat is een GPU eigenlijk?)

We willen vermijden dat tijdens de uitvoering de processor vastlopt of het geheugen op is.

“Ik heb altijd ofwel te weinig tijd, of te weinig geheugen.”

• De last van een algoritme voor de processor kunnen we inschatten met de “Time Complexity”
• De last van een algoritme voor het werkgeheugen kunnen we inschatten met de “Space Complexity”

Dit zijn theoretische schattingen. Je kan looptijdbeslissingen niet voorspellen (bv. “conditionals” of user input). De complexiteit is dus een benadering; een soort van “worst case” schatting.

Wij gaan dit hier niet doen. Enkele toevallig gevondene bronnen voor geïnteresseerden:

• https://towardsdatascience.com/understanding-time-complexity-with-python-examples-2bda6e8158a7
• https://www.studytonight.com/data-structures/space-complexity-of-algorithms

We kunnen de Rij van Fibonacci op meerdere manieren implementeren. De looptijd hangt duidelijk af van de gekozen algoritme.

• werkbestand van tijdens de les: hier downloaden

# naive implementatie: Fibonacci-rij
# Fibonacci-Rij
def Fibonacci1(n):
    # base case
    if (n == 0) or (n == 1):
        return n

    # anders: som van de vorige twee elementen
    return Fibonacci1(n-1) + Fibonacci1(n-2)


def Fibonacci2(n):
    # base case
    if (n == 0) or (n == 1):
        return n


    rij = [0]*(n+1) # een lege lijst met de lengte n+1
    # geef de eerste twee elementen
    rij[0] = 0
    rij[1] = 1

    # rij aanvullen
    for i in range(2, n+1):
        rij[i] = rij[i-1]+rij[i-2]
    return rij[-1]


# de tijd meten die een functie nodig heeft
from time import time
looptijden = []
for i in range(40):
    starttijd = time()
    fib = Fibonacci1(i)
    eindtijd = time()
    print(i, fib, eindtijd-starttijd)
    looptijden.append(eindtijd-starttijd)

import matplotlib.pyplot as PLT
PLT.plot(looptijden)

PLT.gca().set_xlabel('Fibonacci(n) recursief')
PLT.gca().set_ylabel('tijd t (s)')
PLT.gca().spines[['top', 'right']].set_visible(False)
PLT.gcf().savefig('../img/fibonacci_looptijden.svg', dpi = 100, transparent = False)
PLT.show()