Algoritmo online
In informatica, con la locuzione algoritmo online si intende un algoritmo, per la risoluzione di un problema, che deve fornire dei risultati pur non avendo a disposizione, inizialmente, alcuni dei dati in ingresso.
Più precisamente, l'algoritmo riceve in ingresso una generica sequenza σ di input di cui, per ogni termine σi, deve fornire una risposta o prendere una decisione, basandosi solo sugli input ricevuti fino a tale istante, σj con j ≤ i.
A questa tipologia si contrappone la definizione di algoritmo offline che designa i classici algoritmi, i quali possiedono tutti i dati d'ingresso fin dall'inizio dell'elaborazione, ovvero tutta la sequenza σ.
Competitività
Mancando alcuni dati di ingresso, il costo della strategia offerta da un'algoritmo online sarà superiore rispetto a quello che un algoritmo offline può offrire. Lo studio dell'efficienza di questo tipo di L'analisi competitiva permette di valutare un parametro detto α-competitività (o c-competitività) di un algoritmo online. Dato un algoritmo online A, il cui costo è CA ed un algoritmo offline ottimo OPT il cui costo è COPT, l'algoritmo A è α-competitivo se per ogni possibile sequenza di input σ si ha:
Dove α e c sono costanti tra loro indipendenti all'aumentare delle quali diminuisce la competitività dell'algoritmo. Nella definizione classica di α-competitività la costante c è assente (ovvero ha valore nullo), la sua introduzione si rende però necessaria in vari contesti.
Note