och
2.1
2/N, 37, Sqrt(N), N, N loglog N, N log N, N log (N^2), N log^2 N,
N^(1.5), N^2, N^2 log N, N^3, 2^(N/2), 2^N.
N log N och N log (N^2) växer asymptotiskt lika snabbt.
2.2
(a) sant
(b) falskt
(c) falskt
(d) falskt
2.3
N log N växer långsammast.
2.4
Svaret givet i uppgiften, beviset lämnas som övning.
2.6
(a) 2^(2^(N-1))
(b) O(loglog D)
2.7
(1) O(n)
(2) O(n^2)
(3) O(n^3)
(4) O(n^2)
(5) O(n^5)
(6) O(n^4)
2.10
(a) O(N)
(b) O(N^2)
(c) Det beror på hur många siffror efter decimalkommat som beräknas.
Varje siffra tar O(N) tid.
2.11
(a) Funktionen är linjär, vi ansätter T(N) = C * N. Eftersom vi vet att T(100) = 0.5 (uttryckt i millisekunder), får vi:
T(100) = C * 100 = 0.5 => C = 0.5/100 => T(500) = C * 500 = 0.5/100 * 500 = 2.5Alltså 2.5 ms.
(b) Funktionen är O(N log N), vi ansätter T(N) = C * N log N. Eftersom vi vet att T(100) = 0.5 (uttryckt i millisekunder), får vi:
T(100) = C * 100 log 100 = 0.5 => C = 0.5/(100 log 100) => T(500) = C * 500 log 500 = 0.5/(100 log 100) * 500 log 500 = 2.5 * log 500 / log 100log 500 är ungerfär 9 och log 100 är ungefär 6.5, så resultatet blir ungefär 3.5 ms.
(c) Funktionen är kvadratisk, vi ansätter T(N) = C * N^2. Eftersom vi vet att T(100) = 0.5 (uttryckt i millisekunder), får vi:
T(100) = C * 100^2 = 0.5 => C = 0.5/100^2 => T(500) = C * 500^2 = 0.5/100^2 * 500^2 = 12.5Alltså 12.5 ms.
(d) Funktionen är kubisk, vi ansätter T(N) = C * N^3. Eftersom vi vet att T(100) = 0.5 (uttryckt i millisekunder), får vi:
T(100) = C * 100^3 = 0.5 => C = 0.5/100^3 => T(500) = C * 500^3 = 0.5/100^3 * 500^3 = 62.5Alltså 62.5 ms.
2.12
(a) Hur mycket hinner vi på 60 000 ms om tidskomplexiteten är linjär?
Vi ansätter T(N) = C * N.
Eftersom vi vet att T(100) = 0.5 (uttryckt i millisekunder), får vi:
T(100) = C * 100 = 0.5 => C = 0.5/100Vi sätter in T(N) = 60 000:
C * N = 60 000
0.5/100 * N = 60 000
Alltså: N = 12 000 000.
(b) Hur mycket hinner vi på 60 000 ms om tidskomplexiteten är O(N log N)?
Vi ansätter T(N) = C * N log N.
Eftersom vi vet att T(100) = 0.5 (uttryckt i millisekunder), får vi:
T(100) = C * 100 log 100 = 0.5 => C = 0.5/(100 log 100)Eftersom log 100 är ungefär 6.5, får vi
C = 0.5 / 650 = 1/1300Vi sätter in T(N) = 60 000:
C * N log N = 60 000
1/1300 * N log N = 60 000
=> N log N = 78 000 000
Vi vet att log 1 000 000 är ungefär 20, och log 4 000 000 är därför
ungeför 22.
Om vi sätter N till 4 000 000 får vi att N log N är ungefär 88 000 000,
så N är lite mindre än 4 000 000.
(c) Hur mycket hinner vi på 60 000 ms om tidskomplexiteten är kvadratisk?
Vi ansätter T(N) = C * N^2.
Eftersom vi vet att T(100) = 0.5 (uttryckt i millisekunder), får vi:
T(100) = C * 100^2 = 0.5 => C = 0.5/10 000 = 1/20 000Vi sätter in T(N) = 60 000:
C * N^2 = 60 000
1/20 000 * N^2 = 60 000
=> N = sqrt(1 200 000 000) = 34 641
Alltså: N = 34 000
(d) Hur mycket hinner vi på 60 000 ms om tidskomplexiteten är kubisk?
Vi ansätter T(N) = C * N^3.
Eftersom vi vet att T(100) = 0.5 (uttryckt i millisekunder), får vi:
T(100) = C * 100^3 = 0.5 => C = 0.5/1 000 000 = 1/2 000 000Vi sätter in T(N) = 60 000:
C * N^3 = 60 000
1/2 000 000 * N^3 = 60 000
=> N = 120 000 000 000^(1/3) = 4932
Alltså: N = 5000
2.22
Beräkna (exempelvis) X^2, X^3, X^5, X^10, X^20, X^40, X^60 och X^62.
Extra 1
Stacken ser ut så här (stacktoppen visas överst):
H
E
J
4.1
(a) A
(b) G, H, I, L, M och K
4.2
För nod B:
(a) A
(b) D och E
(c) C
(d) 1
(e) 3
4.3
Djupet är 4
4.4, 4.5 och 4.6
Svaret givet, beviset lämnas som övning.
4.8
(a) - * * a b + c d e
(b) ((a * b) * (c + d)) - e
(c) a b * c d + * e -
4.9
Bågarna får du tänka dig.
(a)
3
1 4
2 6
5 9
7
4
1 6
2 5 9
7
Extra 2
D:98
A:101 K:111
C:233 G:200 N:144
J:235 M:188
Extra 3
Det finns mångs möjligheter.
5.1
(a) Vi antog här att nya element läggs sist i listorna, man kan ju förstås lägga dem först i stället.
0: 1: 4371 2: 3: 1323 6173 4: 4344 5: 6: 7: 8: 9: 4199 9679 1989
(b)
0: 9679 1: 4371 2: 1989 3: 1323 4: 6173 5: 4344 6: 7: 8: 9: 4199
(d) 1989 kan inte sättas in eftersom hash_2 (1989) = 6 och de alternativa positionerna 5, 1, 7 och 3 alla är upptagna. Hashtabellen ser ut så här:
0: 1: 4371 2: 3: 1323 4: 6173 5: 9679 6: 7: 4344 8: 9: 4199
5.2
När vi gör re-hashning, väljer vi en tabellstorlek som är ungefär dubbelt så sor och dessutom primtal. I detta fall är 19 ett bra val. Hashfunktionen är h(x) = x mod 19.
(a)
0: 4199 1: 4371 2: 3: 4: 5: 6: 7: 8: 9679 9: 10: 11: 12: 1323 4344 13: 1989 14: 15: 16: 17: 6173 18: 19:
(b)
0: 4199 1: 4371 2: 3: 4: 5: 6: 7: 8: 9679 9: 10: 11: 12: 1323 13: 1989 14: 4344 15: 16: 17: 6173 18: 19:
(d)
0: 4199 1: 4371 2: 3: 4: 5: 6: 7: 8: 9679 9: 10: 11: 12: 1323 13: 1989 14: 15: 4344 16: 17: 6173 18: 19:
5.19
000 001 010 011 100 101 110 111
| / | / | | \ |
| / | / | | \ |
(2 (2) (3) (3) (2)
00000010 01010001 10010110 10111101 11001111
00001011 01100001 10011011 10111110 11011011
00101011 01101111 10011110 11110000
01111111
6.2
(a)
1
3 2
6 7 5 4
15 14 12 9 10 11 13 8
1
3 2
12 6 4 8
15 14 9 7 5 11 13 10
6.3
(a)
4
6 5
13 7 10 8
15 14 12 9 11
4
6 5
12 7 10 8
15 14 9 13 11
6.4
(a) 4N
(b) O(N^2)
(c) O(N^4.1)
(d) O(2^N)
6.6
225 (Man räknar inte alla noder, utan man ser det genom att räkna ut vilken position i vektorn den sista noden skulle ha om man representerade en heap i en vektor.)
6.8 a,c
Bevisen lämnas som övning.
6.13a
Iden är att, efter att man funnit vilken väg man skall bubbla längs, kan man göra en binärsökning längs den vägen i stället för att bubbla. Binärsökning längs en väg av längden log N tar O(loglog N) jämförelser.
10.3
Vi skissar hur det digitala trädet blir, därur kan man utläsa koderna.. Plustecken står för interna noder och löven markeras med citationstecken.
+
+ +
"," + + +
+ + "0" + "sp" +
"4" "7" "8" "9" "1" "5" + +
"nl" + "6" "2"
"3" ":"