Vad är en algoritm?

Question

Vad är en algoritm?

Accepted Answer

En **algoritm** är en ändlig, väldefinierad sekvens av steg som omvandlar indata till önskad utdata. Vi bedömer den på två axlar: **korrekthet** (producerar den alltid rätt svar?) och **effektivitet** (hur mycket tid och minne använder den?).

## Idén

En giltig algoritm måste vara *tvetydig* (varje steg är klart), *ändlig* (den avslutas) och producera *rätt* resultat för varje giltig indata.

## Exempel

```python
# Find the maximum value in a list
def find_max(nums):
    if not nums:
        return None          # handle empty input
    largest = nums[0]        # assume first is the max
    for n in nums[1:]:       # scan the rest
        if n > largest:
            largest = n      # update when we see something bigger
    return largest

find_max([3, 9, 2, 7])       # -> 9
```

Detta besöker varje element en gång.

## Komplexitet

- **Tid:** O(n) — en genomgång av n element.
- **Utrymme:** O(1) — bara en extra variabel.

## När det spelar roll / fallgropar

Samma problem, många algoritmer med olika kostnader. Kontrollera alltid kantfall (tom indata, ett element, dubbletter) — det är där korrekthet vanligtvis går sönder.

## Varför det är viktigt

Algoritmer är kärnan i problemlösning inom mjukvara.

Två program kan producera samma svar medan det ena är tusentals gånger snabbare.

Att tänka i termer av korrekthet *och* effektivitet är det som skiljer kod som fungerar på ett testfall från kod som fungerar i stor skala.

Det är också det gemensamma språket för tekniska intervjuer och systemdesigndiskussioner.