Föreläsning 5 Flashcards
(9 cards)
Vad innebär “divide and conquer”?
- Dela i linjär tid problemet till n/2 subproblem
- Lös varje subproblem
- Kombinera lösningarna till en helhetslösning på linjär tid
Vad är tidskomplexiteten för en “divide and conquer” algorithm?
Θ(n log n)
Den kör alltså alltid på samma tid
Hur kan man räkna antalet “inversions” i en array? Vad är tidskomplexiteten?
Man kan använda divide and conquer, likt med mergesort.
Divide and conquer körs alltid på Θ(n log n)
Vad är “master theorem”?
Ett sätt att hitta asymptotisk tidskomplexitet för divide and conquer algorithmer, som vanligtvis är problematiska pga. rekursion.
Beskriv formeln för Master Theorem
Om T(n) = aT(n/b) + O(n^d)
Får vi T(n) =
1. O(n^d) om d > log_b(a)
2. O(n^d log n) om d = log_b(a)
3. O(n^(log_b(a))) om d < log_b(a)
Förklara “Graham’s Scan” och dess tidskomplexitet
Det är en algorithm för att hitta den minsta polygonen som omsluter alla punkter i ett 2D plan.
- Hitta den punkt a med lägst y-värde
- Sortera alla punkter baserat på vinkeln från a, störst till minst
- Gå igenom varje punkt i stacken
- Om punkt i något steg är till höger, ta bort punkt och hoppa till nästa
- Fortsätt så tills stack är tom
Tidskomplexitet: O(n log n), domineras av sorteringen
Förklara “Jarvis march” och dess tidskomplexitet
Det är en algorithm som likt Graham’s Scan hittar den minsta polygonen som omsluter alla punkter i ett 2D plan.
- Hitta den punkt a med lägst y-värde
- Beräkna vinkeln till andra punkter
- Gå därefter till den punkt längst till höger
- Fortsätt så tills vi når startpunkten
Tidskomplexitet:
Hur kan man kolla riktningen mer effektivt än att beräkna vinkeln direkt?
Man kan beräkna kryssprodukten.
Förklara “Preparata Hong” och dess tidskomplexitet
Det är en algorithm för att hitta den minsta polygonen som omsöuter alla punkter i ett 2D plan. Den är nämnvärd för den använder divide and conquer, och därav går att parallelisera.
