Komplexitäten

Question 1

konstant

Answer 1

• Klasse: 1
• Code: a = b + c
• Beschreibung: einfache Anweisung

Question 2

logarithmisch

Answer 2

• Klasse: log N
• Code: binäre Suche
• Beschreibung: iteratives Halbieren

Question 3

linear

Answer 3

• Klasse: N
• Code:
  ~~~
  for i in range(N):
  print(i)
  ~~~
• Beschreibung: einfache Schleife

Question 4

quasilinear

Answer 4

• Klasse: N log N
• Code: Mergesort
• Beschreibung: “divide and conquer”

Question 5

quadratisch

Answer 5

• Klasse: N^2
• Code:

for i in range(N):
    for j in range(N):

• Beschreibung: doppelte Schleife

Question 6

kubisch

Answer 6

• Klasse: N^3
• Code:
  ~~~
  for i in range(N):
  for j in range(N):
  for k in range(N):
  ~~~
• Beschreibung: dreifache Schleife

Question 7

exponentiell

Answer 7

• Klasse: 2^N
• Code: siehe Hanoi
• Beschreibung: Verdoppelung der Arbeit