järjestysmonotonisuutta

Järjestysmonotonisuus, joka tunnetaan myös nimellä monotonisuus, on matemaattinen käsite, joka kuvaa funktion tai jonon käyttäytymistä suhteessa sen syötteisiin. Yksinkertaisesti sanottuna monotoninen funktio tai jono liikkuu aina samaan suuntaan: joko ylöspäin tai alaspäin. Tätä ominaisuutta hyödynnetään monissa algoritmeissa ja matemaattisissa todistuksissa.

Monotonisuudesta on kaksi päätyyppiä: kasvava monotonisuus ja vähenevä monotonisuus. Kasvava monotoninen funktio tai jono ei koskaan vähene. Kun syöte kasvaa, funktion arvo pysyy samana tai kasvaa. Formaalisti, jos funktio f on kasvava, niin kaikilla x1 ja x2 pätee: jos x1 ≤ x2, niin f(x1) ≤ f(x2). Toisaalta vähenevä monotoninen funktio tai jono ei koskaan kasva. Kun syöte kasvaa, funktion arvo pysyy samana tai vähenee. Formaalisti, jos funktio f on vähenevä, niin kaikilla x1 ja x2 pätee: jos x1 ≤ x2, niin f(x1) ≥ f(x2).

Strictly increasing ja strictly decreasing ovat erikoistapauksia, joissa funktion arvo muuttuu aina syötteen muuttuessa. Strictly increasing -funktioissa jos x1 < x2, niin f(x1) < f(x2), ja strictly decreasing -funktioissa jos x1 < x2, niin f(x1) > f(x2).

Monotonisuuden käsite on perustavanlaatuinen esimerkiksi binäärihaussa, joka edellyttää datan olevan järjestettyä, eli monotonista. Se auttaa myös todistamaan funktioiden ominaisuuksia ja analysoimaan niiden käyttäytymistä laajemmalla syötearvovälillä.