problemstørrelse

Problemstørrelse beskriver størrelsen på et input i en beregningsopgave og er en central parameter i kompleksitetsteori og algoritmedesign. Den angives ofte som n og svarer til længden eller koden af inputtet (for eksempel antallet af elementer, noder i en graf eller antallet af bits i datarepræsentationen).

Problemstørrelsen bestemmer ressourcerne, som en algoritme kræver: tid og hukommelse. I analyse bruges funktioner som T(n) og S(n) til henholdsvis tids- og rumforbrug. Vækstrater beskrives med notation som O(n log n) eller O(n^2); generelt er polynomielle vækstrater mere skalerbare end eksponentielle, når n vokser.

Eksempler: At sortere en liste med n elementer har typisk tid O(n log n); at beregne korteste sti i en graf med n noder og m kan have tid i forhold til n og m. For optimeringsproblemer kan størrelsen af variabler og antallet af begrænsninger definere problemstørrelsen og dermed den forventede beregning.

Praktiske forhold spiller også ind: hardware, I/O, datarepræsentation og numerisk præcision kan ændre den effektive problemstørrelse i praksis. I streaming- eller online-scenarier vokser inputstørrelsen over tid, og analyser fokuserer ofte på vækstmønstre frem for faste grænser.

Relaterede begreber inkluderer inputstørrelse og dimension i data; i nogle sammenhænge omtales også problemkardinalitet og kompleksitet i forhold til dimensionalitet, hvor antallet af dimensioner kan påvirke væksten betydeligt.