Jednoprůchodový algoritmus - One-pass algorithm - Wikipedia
 | tento článek ne uvést žádný Zdroje. (Leden 2007) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) |
Ve výpočetní technice, a jednoprůchodový algoritmus je streamovací algoritmus který načte svůj vstup přesně jednou, v pořadí, bez omezení ukládání do vyrovnávací paměti. Jednoprůchodový algoritmus obecně vyžaduje Ó(n) (viz „velká O“ notace ) čas a méně než Ó(n) úložiště (obvykle Ó(1)), kde n je velikost vstupu.
V zásadě jednoprůchodový algoritmus funguje následovně:
- Popisy objektů jsou zpracovávány sériově
- První objekt se stává zástupcem prvního klastru
- Každý následující objekt je porovnán se všemi zástupci klastru, kteří existují v době zpracování
- Daný objekt je přiřazen k jednomu klastru (nebo více, pokud je povoleno překrytí) podle určitých podmínek funkce párování
- Když je objekt přiřazen ke klastru, zástupce pro tento klastr se přepočítá
- Pokud objekt selže při určitém testu, stane se představitelem klastru nového klastru, nic se nestalo
Ukázkové problémy řešitelné jednoprůchodovými algoritmy
Vzhledem k jakémukoli seznamu jako vstupu:
- Spočítejte počet prvků.
Vzhledem k seznamu čísel:
- Najít k největší nebo nejmenší prvky, k dané předem.
- Najít součet, znamenat, rozptyl a standardní odchylka prvků seznamu. Algorithms_for_calculating_variance
Vzhledem k tomu, seznam symbolů z abecedy k předem dané symboly.
- Spočítejte, kolikrát se každý symbol objevil na vstupu.
- Najděte nejvíce nebo nejméně časté prvky.
- Seřadit seznam podle určitého pořadí na symbolech (možné, protože počet symbolů je omezený).
- Najděte maximální mezeru mezi dvěma vzhledy daného symbolu.
Ukázkové problémy neřešitelné jednoprůchodovými algoritmy
Vzhledem k jakémukoli seznamu jako vstupu:
- Najít nth element od konce (nebo nahlásit, že seznam má méně než n elementy).
- Najděte prostřední prvek seznamu.
Vzhledem k seznamu čísel: