APP-Notes

• Algorithm analyses
  • Datastructuren
  • Complexiteit
    • Factoren
    • Orde
  • Logaritmische functie
• Opdrachten
  • 5.6
  • 5.4
  • 5.14
  • 5.15
    • Roots
  • 5.20
    • a

Algorithm analyses

“Clearly specified set of simple instructions to be followed to solve a problem”

Datastructuren

• Houden gegevens vast voor een gegeven probleem
• Is een manier om data te structureren

Complexiteit

Factoren

• CPU
• OS
• Kwaliteit van code/algoritme
• Input
• Geheugen
  • Zowel code als datastructuren moeten in geheugen passen

Orde

De looptijd van deze for-lus is orde-n, of kort: O(n) (= Big Oh notatie)

• (int i = 0; i < n; i++)
  • O(n)
• (int i = 0; i < n*n; i++)
  • O(n²)
• (int i = 0; i < 0.5 * n; i++)
  • O(n)

Logaritmische functie

• TODO

Opdrachten

5.6

O(N)

5.4

| x | Big Oh | |:———–|:——-| | x² | O(n²) | | x | O(n) | | x²+x | O(n²) | | x²-x | O(n²) | | (x^3/(x-1)) | O(n²) |

5.14

• a: 2.5 ms
• c: 12,5 ms
• d: 62,5 ms

5.15

• a: 12.000.000
• c: 34.641,01615
• d: 4.932,4241

Roots

• square of cubic root van (<doel-ms> / <ms voor 1 input>)
• x^(1/3) == cubic root

5.20

a

| Fragment | Big-Oh | | ——– | ——– | | 1 | O(n) | | 2 | O(n) | | 3 | O(n²) | | 4 | O(n) | | 5 | O(n^3) | | 6 | O(n²) | | 7 | O(n^5) | | 8 | O(log n) |