3 studenten schreven elk een functie die het grootste getal in een lijst teruggeeft:
# Overloopt elk element en kijkt of dit het maximum is.
def max1(lijst):
for x in lijst:
grootste = True
for y in lijst:
if y > x:
grootste = False
if grootste:
return x
# doorloopt de lijst en houdt voorlopig maximum bij
def max2(lijst):
grootste = lijst[0]
for x in lijst:
if x > grootste:
grootste = x
return grootste
# verdeel en heers strategie
def max3(lijst):
if len(lijst) == 1:
return lijst[0]
midden = len(lijst) // 2
max_links = max3(lijst[:midden])
max_rechts = max3(lijst[midden:])
if max_links > max_rechts:
return max_links
return max_rechts
Geef van elke functie de tijdscomplexiteit, met een uitleg van hoe je eraan komt. Kopieer onderstaand kader in het invoerveld om je antwoorden in te vullen.
# max1(lijst)
# tijdscomplexiteit: <jouw antwoord>
# verklaring: <jouw antwoord>
# max2(lijst)
# tijdscomplexiteit: <jouw antwoord>
# verklaring: <jouw antwoord>
# max3(lijst)
# tijdscomplexiteit: <jouw antwoord>
# verklaring: <jouw antwoord>