Konstanta tempo

En komputa komplikteorio, konstanta tempo, aŭ la kalkulada tempo de problemo O(1) estas okazo ke la tempo bezonata por solvi la problemon ne dependas de amplekso de la datumoj donitaj kiel enigo, aŭ dependas sed en ĉiuj okazoj la tempo estas ne pli granda ol iu deantaŭe sciata valoro.

Ekzemple, atingo de ĉiu sola ero en tabelo prenas konstantan tempo ĉar nur unu operacio devas esti farita. Tamen, trovo de minimuma valoro en neordigita tabelo estas ne konstanta tempa operacio ĉar necesas skani tra ĉiuj eroj en la tabelo por trovi la minimuman valoron, kaj ĉi tio estas des pli daŭra ju pli granda estas la tabelo.

Tamen, se la kvanto de eroj estas sciata antaŭe kaj ne estas konsiderata kiel la argumento por pritaksi komplikecon, pri ĉi tia serĉo de minimuma valoro eblas diri ke ĝi havas konstantan tempon. Ekzemple, estu donita n×5 matrico. Tiam por trovi minimuman eron en la unua kolumno (la kolumno konsistas el n eroj) bezonatas tempo O(n) (ne konstanta tempo), kaj por trovi minimuman eron en la unua linio (la linio konsistas el 5 eroj) bezonatas tempo O(1) (konstanta tempo).

Vidu ankaŭRedakti