Algorytm online – szczególny rodzajalgorytmu, który nie zna danych wejściowych od początku w całości, lecz otrzymuje je w partiach (turach). Po każdej turze algorytm musi podać częściową odpowiedź.

Problemy rozwiązywane przez algorytmy online nazywa sięproblemami online. Naturalnymi przykładami są przydział czasu lub pamięci procesora (scheduling) – ponieważ na ogół nie wiadomo, jakie procesy będą w przyszłości żądać zasobów, konieczne jest przydzielanie ich tylko na podstawie obecnej sytuacji.

Bardziej matematycznym przykładem jestkolorowanie grafu online – startując od grafu pustego, w każdej turze dodaje się pojedynczy wierzchołek ze wszystkimi krawędziami. Zadaniem algorytmu jest wybrać dla niego kolor tak, aby kolorowanie byłodopuszczalne i kolorów było możliwie najmniej.

Algorytmami online nazywa się też te algorytmy klasyczne, które nie potrzebują czytać całych danych wejściowych, lecz mogą je przetwarzać na bieżąco. Takimi algorytmami są np.algorytm KMP dopasowania wzorca, czyalgorytm Ukkonena konstrukcjidrzewa sufiksowego.

Oczywiście, znając od początku pełne dane, prawdopodobnie udałoby się znaleźć lepsze rozwiązanie danego problemu (bardziej efektywny przydział pamięci, mniej użytych kolorów). Dlatego też zasadne jest porównywanie rozwiązania podanego przez algorytm online z optymalnym rozwiązaniem na tych samych danych wejściowych.

Jeśli dla każdych możliwych danych algorytm online daje wynik co najwyżej${\displaystyle c}$ razy gorszy niż optymalny, mówimy, że algorytm jest${\displaystyle c}$-konkurencyjny. Liczba${\displaystyle c}$ nazywa sięwspółczynnikiem konkurencyjności algorytmu.

Uogólnieniem tego pojęcia jestfunkcja konkurencyności: jest to taka funkcja${\displaystyle f,}$ że dla dowolnych danych wejściowych algorytm online daje wynik nie gorszy niż${\displaystyle f(w),}$ gdzie${\displaystyle w}$ jest wynikiem optymalnym.

• Algorytmika