Algoritmo lineare
Un algoritmo lineare è un algoritmo debolmente polinomiale che impiega un tempo pari a O ( n ) per elaborare n dati in ingresso. E' quindi un algoritmo polinomiale in cui il parametro k sia pari a uno ( k=1 ) e la complessità sia pari a O ( n1 ). L'algoritmo lineare è anche conosciuto come algoritmo tempo lineare. L'algoritmo lineare ha una complessità lineare. Questa caratteristica è possieduta da tutti gli algoriti in cui il numero di operazioni O ( n ) cresce in modo proporzionale al numero n di bit dei dati ( dimensione dei dati ) da analizzare. Esempi di algoritmi lineari sono la ricerca squenziale e il merge di due file.
