Sublineær

Sublineær, eller sublinear på dansk, betegner i matematik og informatik egenskaber ved funktioner eller vækstmønstre, der vokser eller måles langsommere end lineært. En funktion f: V → R anses for at være sublineær hvis den opfylder tre betingelser: f(0) = 0, f(x+y) ≤ f(x) + f(y) for alle x, y, og f(αx) = α f(x) for alle α ≥ 0 og alle x. Disse krav gør f både subadditiv og positivt homogeneous af grad 1. Sublineære funktioner er generelt konvekse, og en central relation er at støttefunktionen til en konveks mængde C, defineret ved σ_C(y) = sup_{x∈C} ⟨y,x⟩, er sublineær.

Eksempler er vigtige: Normer er sublineære, idet de tilfredsstiller trekantsuafhængighed og homogene egenskaber. Minkowskifunktional til en konveks mængde er også sublineær. Lineære funktioner er automatisk sublineære og ofte brugt som en simpel specialcase.

Udbredt anvendelse findes i optimering og funktionalanalyse, hvor sublineære funktioner spiller en central rolle i dualitet og begrænsninger. Begrebet bruges også i beskrivelsen af vækst og omkostningsfunktioner, hvor mindre end lineær vækst betegnes som sublineær.

I datalogi tale om sublinear tid: tidskompleksitet som vokser langsommere end størrelsen af input, for eksempel log n, hvilket giver algoritmer der ikke læser hele input. Sublineære egenskaber er derfor centrale i både teoretiske og anvendte sammenhænge.