3784495073

A może mamy algorytm najlepszy?

Podsumowanie:

Mamy dwa algorytmy znajdowania min lub max:

•    przeszukiwanie liniowe

•    rozegranie turnieju

które na zbiorze n elementów wykonują n - 1 porównań

Może nie ma szybszego algorytmu?

TAK!    Hugo Steinhaus tak to uzasadnił:

Jeśli Tomek jest zwycięzcą turnieju, w którym startuje n zawodników, to każdy inny spośród n- 1 zawodników musiał przegrać przynajmniej raz, a zatem rozegrano przynajmniej n- 1 meczy. Zatem każdy algorytm musi wykonać przynajmniej n- 1 porównań, czyli nasze algorytmy są najszybsze - są optymalne.

19

informatyka +