Algoritmer

• Detaljerade instruktioner för att utföra en uppgift
• Alla program är egentligen algoritmer
• Vanligtvis: abstrakta, generella uppgifter
  • Sökning
  • Sortering
  • Grafer

Sökning

1. public static int FindIndex(int[] array, int target) {
2. for (int i = 0; i < array.Length; i += 1) {
3. if (array[i] == target) {
4. return i;
5. }
6. }
8. // Will only run if nothing is found.
9. // In that case, use -1 to mean "not found".
10. return -1;
11. }

Hastighet

• Om listan har 100 värden, hur många iterationer kör loopen?
  • I bästa fall
  • I värsta fall
  • I genomsnitt

Högre hastighet

• Kan vi göra det snabbare?
  • Nej, vi måste alltid kolla varje värde
• ... men om listan är sorterad?

Binärsökning

• Kolla mittersta värdet
• Är det högre än sökvärdet?
  • Fortsätt med vänstra halvan
• Är det lägre än sökvärdet?
  • Fortsätt med högra halvan
• Fortsätt tills sista värdet är nått

Hastighet på binärsökning

• Om listan har 100 värden, hur många iterationer kör loopen?
  • I bästa fall
  • I värsta fall
  • I genomsnitt

Binärsökning i C#

1. // Requires the array to be sorted.
2. // Probably contains off-by-one errors.
3. public static int BinaryFindIndex(int[] array, int target) {
4. int first = 0;
5. int last = array.Length - 1;
6. int middle = last / 2;
8. while (first != last) {
9. if (array[middle] == target) {
10. return middle;
11. }
12. else if (array[middle] > target) {
13. last = middle;
14. }
15. else {
16. first = middle;
17. }
18. int difference = last - first;
19. middle = first + (difference / 2);
20. }
22. return -1;
23. }

Algoritmdesign

• Lösa problemet
  • Hur hittar vi rätt svar?
• Lösa problemet snabbt
  • Hur hittar vi svaret så snabbt som möjligt?

Varför hastighet är viktigt

• Moderna datorer är jättesnabba och blir ännu snabbare
• Varför bry sig om hastighet?
  • Många problem har en astronomisk mängd tänkbara lösningar
  • Storleken på problemet ökar snabbare än datorutvecklingen
  • Hela grunden för kryptografi och datorsäkerhet
• De flesta problem går inte att lösa med "brute force"

Big O

• Matematisk beskrivning av en algoritms hastighet
• n = storleken på indatan
  • längd på lista
  • längd på sträng
  • vanligtvis längd på något
• O(n) = fördubblad indata kräver dubbel extra tid
• O(n²) = fördubblad indata kräver kvadratisk extra tid
• O(n!) = fördubblad indata kräver ofattbar extra tid

Sortering

• Vissa metoder är snabbare i genomsnitt
• Vissa metoder är snabbare i bästa/värsta fall
• Vissa metoder kräver mer minne
• Vissa metoder är enklare att implementera
• Vissa metoder är snabbare i specifika situationer

Algoritmer som ni har skrivit

• Hitta största värdet i en lista (lektion 4, övning 4)
• Hitta vanligaste värden i en lista (lektion 4, övning 7)
• Nästan vad som helst under de stående övningarna

Metodik

• Hitta svaret, oavsett hastighet
  • Tekniker för detta är ett helt studiefält
• Gör algoritmen snabbare
  • Även detta ett helt studiefält

Praktiska tips

• Se om problemet redan är löst
  • Inbyggt i språket
  • I tredjepartsbibliotek
  • Abstrakt beskrivning
• Om datamängden är liten, lös med "brute force"
• Om hastigheten är för låg:
  • Går svaret att beräkna en enda gång och spara?
  • Annars: förbered er på att klura!