Algorytm online

Algorytm online – szczególny rodzaj algorytmu, 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 jest kolorowanie 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ło dopuszczalne 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, czy algorytm Ukkonena konstrukcji drzewa sufiksowego.

Konkurencyjność

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 $c$ razy gorszy niż optymalny, mówimy, że algorytm jest $c$-konkurencyjny. Liczba $c$ nazywa się współczynnikiem konkurencyjności algorytmu.

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