pituusfunktio

Pituusfunktio on käsite, joka tarkoittaa tietojoukosta tai avaimesta riippuen objektin koon tai mittasuhteen antavaa funktionaalista arvoa. Käytännössä pituusfunktio antaa objektille ei-negatiivisen kokonaisluvun, joka kuvaa esimerkiksi sanallisen tai matemaattisen rakenteen kokoa.

Yleinen esimerkki on pituus funktio kirjoitetussa merkkijonossa. Tapahtumaympäristössä Σ*-merkkijonot over algebra, pituusfunktio L: Σ* → N määritellään siten, että L(w) on merkkijonon w merkkien määrä. Perusarvot ovat L(ε) = 0 ja L(uv) = L(u) + L(v). Pituusfunktio mittaa usein järjestelmän varaumaa, muistia tai koodauspituutta. Pituuden laskeminen vaatii käytännössä syötteen lukemisen, mutta tallennetulla pituudella hakeminen on usein O(1).

Toisessa kontekstissa pituus viittaa polun pituuteen grafissa. Polun P pituus L(P) voidaan määritellä lukumääränä sen sisältämien kaarien lukumääränä tai painotetussa verkossa painojen summana: L(P) = k tai L(P) = ∑ w(e), jossa e on polussa esiintyvä kaari.

Geometriassa ja analysissä arc length eli kaaren pituus määritellään usein integraalilla: jos curve γ on derivoituva funktio, pituus L(γ) = ∫_a^b ||γ'(t)|| dt. Tämä laajentaa pituusfunktion käsitteen tavoittamaan jatkuvat muotonsa.

Lopulta pituusfunktio voi esiintyä myös algebra- tai representation-teorian konteksteissa, jossa puhutaan olioiden koostepituudesta tai muusta sijaistavasta mittauksesta. Yleisesti se on käsite, joka kuvaa objektin määrällistä kokoa ja jossa arvo on usein osa suuremmasta rakennetta, kuten monoidin, graafin tai topologisen/todellisuudellisen rakenteen mittausta.