Uppgift 8
Uppgiften ska lämnas till din övningsledare på övningen 19,20/11.
För godkänt måste du ha gjort samtliga deluppgifter.
Det är tillåtet att göra enstaka fel och misstag men det
är viktigt att du försöker lösa samtliga uppgifter.
Hemuppgift
Studera kapitel 6 i programmeringsboken. Den här gången finns
det inga obligatoriska uppgifter från boken men det är naturligtvis
fritt fram att göra uppgifterna på egen hand. Glöm inte heller att
utnyttja labbar och övningar för frågor och diskussioner.
Studera texterna om
tidskomplexitet och
asymptotisk notation.
Skriftlig uppgift
-
Lägg till en implementation av följande sorteringsalgoritm i projektet
sort.jar. Glöm inte att uppdatera
testkoden så att den även testar den nya algoritmen.
Lämna in en utskrift av den modifierade klassen
Sort
.
Algorithm insertionsort(A, n):
Input: An array A storing n integers.
Output: An array with the same integers in ascending order.
for i = 1 to n-1
// Loop invariant: A[0..i-1] is sorted.
Move A[i] to its correct position
within the subarray A[0..i]
- Ordna funktionerna i följande lista i växande ordning med
avseende på tillväxtstakt. Funktionen f(n) ska alltså
komma före funktionen g(n) i listan om
f(n) är O(g(n)).
- f1(n) = n1.5
- f2(n) = 10n
- f3(n) = n log n
- f4(n) = n +100
- f5(n) = 2n
- Vilka av följande påståenden är sanna? Motivera ditt svar.
- n(n + 1) / 2 = O(n3)
- n(n + 1) / 2 = O(n2)
- n(n + 1) / 2 = Θ(n3)
- n(n + 1) / 2 = Ω(n)
-
Indata är en heltalsvektor A med n element.
Vi vill beräkna en vektor B, där B[i] =
A[0] + A[1] + ... + A[i].
Här är en enkel algoritm som löser problemet.
for i = 0 to n-1
Add the numbers A[0] thru A[i].
Store the result in B[i].
-
Beräkna tidskomplexiteten för denna algoritm och uttryck den på
formen O(f(n)), där funktionen f(n)
är så liten och enkel som möjligt.
-
Visa att tidskomplexiteten också är Ω(f(n)).
-
Hitta på en algoritm med bättre asymptotisk tidskomplexitet.
Beskriv algoritmen i pseudokod och ange dess
tidskomplexitet med O-notation.
-
Ge ett exempel på en positiv funktion f(n) sådan att
f(n) varken är O(n) eller
Ω(n).