Föreläsning 2 Flashcards
(7 cards)
1
Q
Vad innebär Ω(n)?
A
Hur tidskomplexiteten hos en funktion växer i bästa fallet. Det är en lägre gräns för hur effektiv funktionen är då n->inf.
2
Q
Vad innebär O(n)?
A
Hur tidskomplexiteten hos en funktion växer i värsta fallet. Det är en övre gräns för hur effektiv funktionen är då n->inf.
3
Q
A
4
Q
Vad är graden av en nod?
A
Antalet kanter som möter en viss nod, eller antalet grannar till en nod om alla kanter leder till en unik nod.
5
Q
Vad innebär en starkt kopplad graf?
A
Från varje nod n kan man nå varje annan nod k
6
Q
Vad är Tarjan’s algoritm?
A
En algoritm för att hitta SSC:s i en riktad graf. Den har tidskomplexitet O(n+m) och kan användas för att avgöra om en graf är starkt kopplad.
7
Q
Hur ser man ifall en graf är cyklisk?
A
Man kan använda hare och sköldpadda algoritmen
