Kaj je algoritem?

Question

Kaj je algoritem?

IT Interview Practice · Accepted Answer

**Algoritem** je končno, dobro opredeljeno zaporedje korakov, ki pretvori vhod v željeni izhod. Ocenjujemo ga na dveh oseh: **pravilnost** (ali vedno proizvedu pravi odgovor?) in **učinkovitost** (koliko časa in pomnilnika porabi?).

## Ideja

Veljavni algoritem mora biti *nedvoumen* (vsak korak je jasen), *končen* (se zaključi) in proizvede *pravi* rezultat za vsak veljaven vhod.

## Primer

```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
```

To obišče vsak element enkrat.

## Zapletenost

- **Čas:** O(n) — en prehod čez n elementov.
- **Prostor:** O(1) — le ena dodatna spremenljivka.

## Kdaj je to pomembno / pasti

Isti problem, mnogo algoritmov z različnimi stroški. Vedno preverite robne primere (prazen vhod, en element, podvojeni elementi) — tam se pravilnost ponavadi zlomi.

## Zakaj je to pomembno

Algoritmi so jedro reševanja problemov v programski opremi.

Dva programa lahko proizvedeta isti odgovor, medtem ko je eden tisočkrat hitrejši.

Razmišljanje v smislu pravilnosti *in* učinkovitosti je tisto, kar loči kodo, ki deluje na testnem primeru, od kode, ki deluje v obsegu.

To je tudi skupni jezik tehničnih intervjujev in diskusij o oblikovanju sistemov.

Ideja

Primer

Zapletenost

Kdaj je to pomembno / pasti

Zakaj je to pomembno

Povezana vprašanja