Co je algoritmus?

Question

Co je algoritmus?

Accepted Answer

**Algoritmus** je konečná, jasně definovaná posloupnost kroků, která transformuje vstup na požadovaný výstup. Hodnotíme jej na dvou osách: **správnost** (vždy produkuje správný výsledek?) a **efektivita** (kolik času a paměti používá?).

## Idea

Platný algoritmus musí být *jednoznačný* (každý krok je jasný), *konečný* (končí) a produkovat *správný* výsledek pro každý platný vstup.

## Příklad

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

Tímto způsobem se každý prvek navštíví jednou.

## Složitost

- **Čas:** O(n) — jeden průchod přes n prvků.
- **Prostor:** O(1) — pouze jedna dodatečná proměnná.

## Kdy je to důležité / úskalí

Stejný problém, mnoho algoritmů s různými náklady. Vždy zkontrolujte hraniční případy (prázdný vstup, jeden prvek, duplikáty) — zde se správnost obvykle porušuje.

## Proč je to důležité

Algoritmy jsou jádrem řešení problémů v softwaru.

Dva programy mohou produkovat stejný výsledek, zatímco jeden je tisíckrát rychlejší.

Myslet na správnost *a* efektivitu je to, co odlišuje kód, který funguje na testovacím případu, od kódu, který funguje v měřítku.

Je to také sdílený jazyk technických pohovorů a diskusí o návrhu systémů.