polynomisktids

Polynomisk tids, oftast kallad polynomisk tidskomplexitet, är ett mått på hur lång tid en algoritm tar i förhållande till storleken på indata. En algoritm sägs köras i polynomisk tid om dess tidsåtgång T(n) övre begränsas av en polynomfunktion i n: det finns konstanter c > 0 och k ≥ 1 such att T(n) ≤ c · n^k för alla tillräckligt stora n. Här betecknas n som storleken på indata, till exempel antal tecken eller antal element i en uppsättning.

Polynomisk tid används som en praktisk standard för vad som anses vara räknarbart effektivt i praktiken. I teoretisk datalära definieras en klass, P, som innehåller de problem som kan lösas i polynomisk tid av en deterministisk dator (eller Turingmaskin). Många vanliga problem faller inom P, exempelvis sortering av n element med mergesort eller heapsort i O(n log n) tid, och beräkningar som att hitta största gemensamma delaren med Euclids algoritm, vilket är polynomiskt i indata storlek.

Relation till andra begrepp: problem som inte är kända att lösas i polynomisk tid klassificeras ofta som NP-fullständiga, vilket innebär att deras polynomiska lösning uppskattas vara osannolik men ännu inte bevisat utesluten. Begreppet polynomisk tid används därmed som en central referens för effektivitet i algoritmer och som grund i P vs NP-diskussionen.

Viktiga nyckelaspekter är att tidsmått används i termer av indata storlek n och att polynomisk tid innebär att tiden växer som en n-funktion upphöjd till en konstant, vilket generellt anses hanterbart för praktiska problemstorlekar.

---