| 1 | Rick van der Zwet, Universiteit Leiden
|
|---|
| 2 | StudentID: 0433373
|
|---|
| 3 | Version: $Id: opdracht-1.txt 561 2008-04-12 13:55:24Z rick $
|
|---|
| 4 | Complexiteit 2008 --- opdracht 1
|
|---|
| 5 |
|
|---|
| 6 | a. Ga na hoe het algoritme werkt voor het array 5,6,1,2,3,4. Laat zien
|
|---|
| 7 | hoe het array eruit ziet _elke_ keer nadat regel (10) is uitgevoerd.
|
|---|
| 8 | N.B: Buurt 0 is de beginstand
|
|---|
| 9 |
|
|---|
| 10 | B: Array - Indexgetal
|
|---|
| 11 | 0: 5.6.1.2.3.4 - 6
|
|---|
| 12 | 1: 5.6.1.4.3.2 - 6
|
|---|
| 13 | 2: 5.2.1.4.3.6 - 6
|
|---|
| 14 | 3: 5.2.1.4.3.6 - 6
|
|---|
| 15 | 4: 5.2.3.4.1.6 - 5
|
|---|
| 16 | 5: 1.2.3.4.5.6 - 5
|
|---|
| 17 | 6: 1.2.3.4.5.6 - 5
|
|---|
| 18 | 7: 1.2.3.4.5.6 - 4
|
|---|
| 19 | 8: 1.2.3.4.5.6 - 3
|
|---|
| 20 | 9: 1.2.3.4.5.6 - 2
|
|---|
| 21 |
|
|---|
| 22 |
|
|---|
| 23 |
|
|---|
| 24 | b. Toon aan dat vergelijken van array-elementen in regel (7) een goede
|
|---|
| 25 | basisoperatie is ,als n >= 0, in orde van grootte.
|
|---|
| 26 |
|
|---|
| 27 | #08 <= #07
|
|---|
| 28 | #09 == #07
|
|---|
| 29 | #06 == #07 + 1
|
|---|
| 30 | #05 <= #06
|
|---|
| 31 | #10 <= #06
|
|---|
| 32 | #11 == #10
|
|---|
| 33 | #12 <= #11
|
|---|
| 34 | #04 == #05 + 1
|
|---|
| 35 | #03 <= #04
|
|---|
| 36 | #13 <= #04
|
|---|
| 37 | #12 == #13 + 1
|
|---|
| 38 | #01 == 1
|
|---|
| 39 |
|
|---|
| 40 |
|
|---|
| 41 |
|
|---|
| 42 | c. Regel (10) kan maximaal 2n - 2 keer worden uitgevoerd. Leg uit
|
|---|
| 43 | waarom. Gebruik dit resultaat om een redelijke bovengrens te bepalen
|
|---|
| 44 | voor het aantal vergelijkingen tussen array elementen (regel (7)).
|
|---|
| 45 |
|
|---|
| 46 | Voor het goede resultaat zal eerst de worst case bepaald moeten worden
|
|---|
| 47 | als gekeken wordt naar regel (10). Hierbij is het verwisselingen dat toe
|
|---|
| 48 | moet passen als alle getallen verkeerd staan n - 1 (het laatste getal
|
|---|
| 49 | staat automatisch goed). Verder moet er nog n - 1 gewisseld worden,
|
|---|
| 50 | hierbij gaat het echter om de 'controle' wissel en zal deze wissel
|
|---|
| 51 | wezelijk dus niets veranderen het rijtje. Bij elkaar opgeteld is 2n - 2
|
|---|
| 52 | dus de eindscore.
|
|---|
| 53 |
|
|---|
| 54 | Om dit resultaat naar het aantal array vergelijkingen te vertalen is het
|
|---|
| 55 | slechte geval het meest aantrekkelijk. Hierbij worden in de 'eerste'
|
|---|
| 56 | index getal (n) de verwisselingen gedaan, dit levert dan telkens n - 1
|
|---|
| 57 | verwisselingen op, subtotaal n^2 - n De controle verwisselingen kosten telkens 1 minder en
|
|---|
| 58 | leveren zo de reeks (n - 1) + (n - 2) + ... + (n - (n -1)) + (n - n) =
|
|---|
| 59 | 0.5n^2 - 0.5n
|
|---|
| 60 | Dit gesommeerd levert op 1.5n^2 - 1.5n
|
|---|
| 61 |
|
|---|
| 62 |
|
|---|
| 63 |
|
|---|
| 64 | d. Best case, met in het antwoord aantal vergelijkingen
|
|---|
| 65 |
|
|---|
| 66 | De best case is een oplopend gesorteerd rijtje, alle getallen staan al
|
|---|
| 67 | op de goede plek, welke enkele de controle vergelijkingen nodig heeft.
|
|---|
| 68 | Dit is 0.5n^2 - 0.5n (zie c.). Tijdens n = 1 worden er 0 vergelijkingen
|
|---|
| 69 | uitgevoerd.
|
|---|
| 70 |
|
|---|
| 71 |
|
|---|
| 72 |
|
|---|
| 73 | e. Worst case, met in het antwoord aantal vergelijkingen
|
|---|
| 74 |
|
|---|
| 75 | De worst case is een rijtje waarbij in de grootste index alle
|
|---|
| 76 | verwisselen gedaan moeten worden (en dus allen verkeerd staan). Zoeen
|
|---|
| 77 | rijtje heeft bijvoorbeeld de vorm 6.0.1.2.3.4.5. Aantal vergelijkingen
|
|---|
| 78 | dat gedaan moet worden is 1.5n^2 - 1.5n (zie e)
|
|---|
| 79 |
|
|---|
| 80 |
|
|---|
| 81 |
|
|---|
| 82 |
|
|---|
| 83 |
|
|---|
| 84 |
|
|---|
| 85 |
|
|---|
| 86 |
|
|---|
