Sekvenslängder

Sekvenslängder är ett mått på hur många element en given sekvens innehåller. Om s är en finite sekvens skrivs s oftast som s = (a1, a2, ..., an) där n är sekvensens längd. För en oändlig sekvens finns ingen finite längd; man säger att längden är oändlig.

Noteringar och begrepp

- Längden skrives vanligtvis som |s| eller len(s). Till exempel har s = (3, 7, 2) längden |s| = 3. Den tomma sekvensen, ofta betecknad ε eller [], har längden 0.

- Efterföljd och sammansättning: om s och t är sekvenser, blir längden av deras sammanfogning s t lika med |s t| = |s| + |t|.

- Undersekvenser: en undersekvens av s består av k element från s i samma ordning. Då gäller 0 ≤ k ≤ |s|.

- Reordning: längden påverkas inte av om man byter ordning på elementen; längden är bara antalet element, inte hur de är ordnade.

- I datavetenskap och programmering används längden ofta för att beskriva tidskomplexitet och arbetsminne. Vissa språk kan returnera längden av en lista eller sträng i konstant tid, andra kräver traversal eller särskild räknning.

Relationer till andra områden

- I formella språk behandlas ord w över alfabetet Σ som w ∈ Σ*, där längden |w| används för att klassificera ord av olika längder och studera mönster i språkets uppbyggnad.

- Strängar och sekvenser används i algoritmer där längden påverkar komplexitet, exempelvis i sök- och sorteringsproblem, eller i beräkning av längder på sekvenser av data.

Sammanfattning

Sekvenslängder beskriver hur många element en sekvens innehåller. De är centrala i teorin om sekvenser, i formella språk och i praktisk programmering där längden ofta styr beteende och prestanda.