Lineara tempo
En komputa komplikteorio, lineara tempo, aŭ la kalkulada tempo de problemo O(n) estas okazo ke la asimptota supera baro de tempo bezonata por solvi la problemon estas proporcia al amplekso n de la datumoj donitaj kiel enigo.
Ekzemple, trovo de minimuma valoro en neordigita tabelo estas lineara tempa operacio ĉar necesas skani tra ĉiuj eroj en la tabelo por trovi la minimuma valoro, kaj ĉi tio estas des pli daŭra ju pli granda estas la tabelo, kaj la daŭro kreskas proporcie kun kvanto de eroj en la tabelo.
Ĉi tiu priskribo estas malpreciza, pro tio ke la rula tempo povas grave dekliniĝi de preciza proporcieco.
- Ĝi povas dekliniĝi por malgrandaj valoroj de n kaj granden kaj malgranden, ĉar estas konsiderata asimptota baro, do por grandaj n.
- Ĝi povas dekliniĝi por ajnaj valoroj de n tiel ke en iuj okazoj reala tempo estas pli malgranda ol proporcia, ĉar estas konsiderata supra baro.
Lineara tempo estas ofte konsiderata kiel dezirinda propraĵo por algoritmo. Multaj esploroj estas farataj por krei algoritmojn kun lineara tempo aŭ pli bona. Ĉi tiuj esploroj inkluzivas ambaŭ programajn kaj aparatarajn manierojn. Iuj algoritmoj kiuj, matematike parolante, ne povas ruli en lineara tempo per kutima komputilo, povas kuri en lineara tempo per speciala aparataro. Estas kelkaj manieroj por krei ĉi tian aparataron kiu faras paraleladon de kalkulado por provizi ĉi tion. La ekzemplo estas asocia memoro.