Powyższy algorytm jest poprawny, ponieważ uporządkowania występują w grupach. Jeśli koalicja graczy jest wygrywająca, natomiast nie, to w wykonywanych wedle definicji obliczeniach wystąpią następujące uporządkowania:
Czyli: wszystkie permutacje gracz (któremu należy się za to 1 punkt), wszystkie permutacje
Ponieważ dla danego zbioru i gracza jest takich permutacji zamiast liczyć je po kolei wystarczy, że sprawdzimy wszystkie zbiory, zamiast wszystkich permutacji.
Złożoność obliczeniowa oryginalnego algorytmu wynosi złożoność zmodyfikowanego zaś
Dla 20 graczy w pierwszym algorytmie trzeba wykonać operacji, w drugim zaś tylko czyli ponad 200 miliardów razy mniej.
Kategoria:Teoria gier