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 razy gorszy niż optymalny, mówimy, że algorytm jest -konkurencyjny. Liczba nazywa się współczynnikiem konkurencyjności algorytmu.
Uogólnieniem tego pojęcia jest funkcja konkurencyności: jest to taka funkcja że dla dowolnych danych wejściowych algorytm online daje wynik nie gorszy niż gdzie jest wynikiem optymalnym.
Kategoria:Algorytmika