Algorytm online

Algorytm online to 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 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ł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.