Analiza efektywności algorytmu

Program działa i wydaje się, że nie ma kłopotów ze znalezieniem NWDNWDNWD dowolnej pary liczb całkowitych. Czy jest tak na pewno? Pierwsze problemy pojawią się, gdy zaczniemy szukać największego wspólnego dzielnika dużych liczb. A jeżeli jedna z liczb w parze jest bardzo duża, a druga bardzo mała, będzie jeszcze gorzej. Program odejmuje od siebie liczby aż do momentu, kiedy staną się one równe. Przy dużej dysproporcji wartości potrzebnych jest wiele przejść pętli. Zajmuje to czas i zasoby komputera.

Załóżmy, że szukamy NWD liczb a = 1 000 000 oraz b = 50 000. Prześledźmy wykonywane operacje:

...

W tym przypadku pętla while wykonała 19 iteracji. Nie jest to zły wynik. Zobaczmy jednak, co się stanie jeżeli spróbujemy znaleźć największy wspólny dzielnik pary 1 000 000 oraz 2.

...

Tym razem pętla while była wykonywana aż 499 999 razy.

Na szczęście istnieje inna wersja algorytmu Euklidesa. Wykorzystywany jest w niej operator modulooperator modulooperator modulo. Prezentacja na kolejnej stronie objaśnia ten właśnie wariant algorytmu.

Słownik