Złożoność czasowa algorytmu Euklidesa


101

Mam trudności z podjęciem decyzji, jaka jest złożoność czasowa największego wspólnego algorytmu mianownika Euclid. Ten algorytm w pseudokodzie to:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

Wydaje się, że zależy to od a i b . Myślę, że złożoność czasowa wynosi O (a% b). Czy to jest poprawne? Czy jest lepszy sposób, aby to napisać?


14
Zobacz Knuth TAOCP, tom 2 - podaje obszerną relację. Tylko FWIW, kilka ciekawostek: to nie jest proporcjonalne do a%b. W najgorszym przypadku są ai bsą to kolejne liczby Fibonacciego.
Jerry Coffin

3
@JerryCoffin Uwaga: Jeśli chcesz udowodnić, że najgorszym przypadkiem są rzeczywiście liczby Fibonacciego w bardziej formalny sposób, rozważ udowodnienie, że n-ty krok przed zakończeniem musi być co najmniej tak duży, jak gcd razy n-ta liczba Fibonacciego z indukcją matematyczną.
Mygod

Odpowiedzi:


75

Jedna sztuczka do analizy złożoności czasowej algorytmu Euclid polega na śledzeniu tego, co dzieje się w dwóch iteracjach:

a', b' := a % b, b % (a % b)

Teraz a i b będą się zmniejszać, a nie tylko jeden, co ułatwia analizę. Możesz podzielić to na przypadki:

  • Małe A: 2a <= b
  • Mały B: 2b <= a
  • Mały A: 2a > balea < b
  • Małe B: 2b > aaleb < a
  • Równy: a == b

Teraz pokażemy, że każdy pojedynczy przypadek zmniejsza sumę a+bo co najmniej jedną czwartą:

  • Tiny A: b % (a % b) < ai 2a <= btak bjest zmniejszona o co najmniej połowę, a więc a+bzmniejszona co najmniej o25%
  • Tiny B: a % b < bi 2b <= atak ajest zmniejszone o co najmniej połowę, a więc a+bzmniejszone co najmniej o25%
  • Małe A: bstanie się b-amniejsze niż b/2, zmniejszając a+bsię co najmniej o 25%.
  • Małe B: astanie się a-bmniejsze niż a/2, zmniejszając a+bsię co najmniej o 25%.
  • Równe: a+bspada do 0, co oczywiście zmniejsza a+bsię co najmniej o 25%.

Dlatego w analizie przypadku każdy podwójny krok zmniejsza a+bsię co najmniej o 25%. Istnieje maksymalna liczba przypadków, w których może się to zdarzyć, zanim a+bzostanie zmuszony do zejścia poniżej 1. Całkowita liczba kroków ( S) do osiągnięcia 0 musi spełnić (4/3)^S <= A+B. Teraz po prostu pracuj:

(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)

Tak więc liczba iteracji jest liniowa względem liczby cyfr wejściowych. W przypadku liczb mieszczących się w rejestrach procesora rozsądne jest modelowanie iteracji jako zajmujących stały czas i udawanie, że całkowity czas działania gcd jest liniowy.

Oczywiście, jeśli masz do czynienia z dużymi liczbami całkowitymi, musisz wziąć pod uwagę fakt, że operacje modułu w każdej iteracji nie mają stałego kosztu. Z grubsza rzecz biorąc, całkowity asymptotyczny czas działania będzie n ^ 2 razy większy niż współczynnik polilogarytmiczny. Coś jak n^2 lg(n) 2^O(log* n) . Można uniknąć współczynnika polilogarytmicznego, używając zamiast tego binarnego gcd .


Czy możesz wyjaśnić, dlaczego „b% (a% b) <a” proszę?
Michael Heidelberg

3
@MichaelHeidelberg x % ynie może być więcej niż xi musi być mniejsze niż y. Tak a % bjest co najwyżej a, zmuszanie b % (a%b)do bycia poniżej czegoś, co jest najwyżej, aa zatem ogólnie jest mniejsze niż a.
Craig Gidney,

@ Cheersandhth.-Alf Uważasz, że niewielka różnica w preferowanej terminologii jest „poważnie błędna”? Oczywiście użyłem terminologii CS; to jest pytanie informatyczne. Niezależnie od tego, wyjaśniłem odpowiedź, mówiąc „liczba cyfr”.
Craig Gidney

@CraigGidney: Dzięki za naprawienie tego. Teraz rozpoznaję problem z komunikacją z wielu artykułów Wikipedii napisanych przez czysto akademickich. Rozważ to: głównym powodem mówienia o liczbie cyfr, zamiast po prostu pisać O (log (min (a, b)), jak to zrobiłem w moim komentarzu, jest ułatwienie zrozumienia rzeczy osobom niematematycznym. Bez tego po prostu napisz „log”, itd. Więc to jest celem liczby cyfr, pomagając tym wymagającym ludziom. Kiedy nazwiesz to pojęcie „rozmiar” i masz definicję gdzie indziej, i nie mów o „logu” w koniec, zasłaniasz zamiast pomagać
Pozdrawiam i hth. - Alf

Ostatni akapit jest nieprawidłowy. Jeśli zsumujesz odpowiednie serie teleskopów, zobaczysz, że złożoność czasowa wynosi po prostu O (n ^ 2), nawet jeśli używasz szkolnego algorytmu dzielenia czasu na kwadrat.
Emil Jeřábek

28

Właściwym sposobem analizy algorytmu jest określenie jego najgorszych scenariuszy. Najgorszy przypadek Euklidesa GCD ma miejsce, gdy w grę wchodzą pary Fibonacciego. void EGCD(fib[i], fib[i - 1]), gdzie i> 0.

Na przykład wybierzmy przypadek, w którym dywidenda wynosi 55, a dzielnik 34 (przypomnijmy, że nadal mamy do czynienia z liczbami Fibonacciego).

wprowadź opis obrazu tutaj

Jak możesz zauważyć, ta operacja kosztowała 8 iteracji (lub wywołań rekurencyjnych).

Wypróbujmy większe liczby Fibonacciego, a mianowicie 121393 i 75025. Możemy również zauważyć, że zajęło to 24 iteracje (lub wywołania rekurencyjne).

wprowadź opis obrazu tutaj

Możesz również zauważyć, że każda iteracja daje liczbę Fibonacciego. Dlatego mamy tak wiele operacji. Nie możemy uzyskać podobnych wyników tylko z liczbami Fibonacciego.

Stąd złożoność czasowa będzie tym razem reprezentowana przez małe Oh (górna granica). Dolna granica jest intuicyjnie Omega (1): na przykład przypadek 500 podzielony przez 2.

Rozwiążmy relację powtarzania:

wprowadź opis obrazu tutaj

Można więc powiedzieć, że Euclidean GCD może co najwyżej wykonać operację log (xy) .


2
Myślę, że ta analiza jest błędna, ponieważ podstawa zależy i od wejścia.
Mam nadzieję, że

Czy możesz udowodnić, że zależna baza stanowi problem?
Mohamed Ennahdi El Idrissi

1
Podstawą jest oczywiście złoty podział. Czemu? Ponieważ obliczenie nod (13,8) vs nod (8,5) wymaga dokładnie jednego dodatkowego kroku. Dla ustalonego x, jeśli y <x, wydajność w najgorszym przypadku to x = fib (n + 1), y = fib (n). Tutaj y zależy od x, więc możemy spojrzeć tylko na x.
Stepan

17

Świetne spojrzenie na to w artykule na Wikipedii .

Ma nawet ładny wykres złożoności dla par wartości.

Nie jest O(a%b).

Wiadomo (patrz artykuł), że nigdy nie wykona więcej kroków niż pięciokrotność liczby cyfr w mniejszej liczbie. Zatem maksymalna liczba kroków rośnie wraz z liczbą cyfr (ln b). Koszt każdego kroku również rośnie wraz z liczbą cyfr, więc złożoność jest ograniczona przez O(ln^2 b)gdzie b jest mniejszą liczbą. To górna granica, a rzeczywisty czas jest zwykle krótszy.


Co noznacza?
IVlad

@IVlad: liczba cyfr. Wyjaśniłem odpowiedź, dziękuję.
JoshD

W przypadku algorytmu OP, stosując (duże liczby całkowite) dzielenia (a nie odejmowania), jest to w rzeczywistości coś więcej niż O (n ^ 2 log ^ 2n).
Alexandre C.

@Alexandre C .: Pamiętaj n = ln b. Jaka jest regularna złożoność modułu dla dużych int? Czy to O (log n log ^ 2 log n)
JoshD

@JoshD: to jest coś takiego, myślę, że przegapiłem termin log n, ostateczna złożoność (dla algorytmu z podziałami) wynosi w tym przypadku O (n ^ 2 log ^ 2 n log n).
Alexandre C.

13

Zobacz tutaj .

W szczególności ta część:

Lamé wykazał, że liczba kroków potrzebnych do uzyskania największego wspólnego dzielnika dla dwóch liczb mniejszych niż n wynosi

tekst alternatywny

Więc O(log min(a, b))jest to dobra górna granica.


4
Odnosi się to do liczby kroków, ale nie uwzględnia złożoności każdego kroku, który skaluje się wraz z liczbą cyfr (ln n).
JoshD

9

Oto intuicyjne zrozumienie złożoności algorytmu Euclid w czasie wykonywania. Formalne dowody są omówione w różnych tekstach, takich jak Wprowadzenie do algorytmów i TAOCP tom 2.

Najpierw zastanów się, co by było, gdybyśmy spróbowali wziąć gcd z dwóch liczb Fibonacciego F (k + 1) i F (k). Możesz szybko zauważyć, że algorytm Euclid iteruje na F (k) i F (k-1). Oznacza to, że z każdą iteracją przesuwamy się o jedną liczbę w dół w szeregu Fibonacciego. Ponieważ liczby Fibonacciego to O (Phi ^ k), gdzie Phi to złoty współczynnik, możemy zobaczyć, że czas wykonania GCD wynosił O (log n), gdzie n = max (a, b), a log ma podstawę Phi. Następnie możemy udowodnić, że byłby to najgorszy przypadek, obserwując, że liczby Fibonacciego konsekwentnie tworzą pary, w których reszty pozostają wystarczająco duże w każdej iteracji i nigdy nie osiągają zera, dopóki nie dojdziesz do początku szeregu.

Możemy sprawić, że O (log n), gdzie n = max (a, b) związane będzie jeszcze mocniej. Załóżmy, że b> = a, więc możemy zapisać ograniczenie w O (log b). Najpierw zauważ, że GCD (ka, kb) = GCD (a, b). Ponieważ największe wartości k to gcd (a, c), możemy zamienić b na b / gcd (a, b) w naszym środowisku wykonawczym, prowadząc do ściślejszego ograniczenia O (log b / gcd (a, b)).


Czy możesz dać formalny dowód, że Fibonacci nos jest najgorszym przypadkiem dla algo Euclids?
Akash

4

Najgorszym przypadkiem algorytmu Euclid jest sytuacja, w której reszty są największe z możliwych na każdym kroku, tj. dla dwóch kolejnych wyrazów ciągu Fibonacciego.

Gdy n i m są liczbą cyfr a i b, zakładając n> = m, algorytm wykorzystuje O (m) działek.

Zwróć uwagę, że złożoność jest zawsze podawana w postaci rozmiarów danych wejściowych, w tym przypadku liczby cyfr.


4

Najgorszy przypadek pojawi się, gdy n i m będą kolejnymi liczbami Fibonacciego.

gcd (Fn, Fn − 1) = gcd (Fn − 1, Fn − 2) = ⋯ = gcd (F1, F0) = 1, a n-ta liczba Fibonacciego to 1,618 ^ n, gdzie 1,618 to złoty współczynnik.

Tak więc, aby znaleźć gcd (n, m), liczba wywołań rekurencyjnych będzie wynosić Θ (logn).


3

Oto analiza w książce Data Structures and Algorithm Analysis in C autorstwa Marka Allena Weissa (drugie wydanie, 2.4.4):

Algorytm Euclid działa na zasadzie ciągłego obliczania reszt aż do osiągnięcia 0. Ostatnia niezerowa reszta to odpowiedź.

Oto kod:

unsigned int Gcd(unsigned int M, unsigned int N)
{

    unsigned int Rem;
    while (N > 0) {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    Return M;
}

Oto TEOREM , którego zamierzamy użyć:

Jeśli M> N, to M mod N <M / 2.

DOWÓD:

Są dwa przypadki. Jeśli N <= M / 2, to ponieważ reszta jest mniejsza niż N, twierdzenie jest prawdziwe w tym przypadku. Drugi przypadek to N> M / 2. Ale potem N przechodzi do M raz z resztą M - N <M / 2, dowodząc twierdzenia.

Możemy więc wyciągnąć następujące wnioski:

Variables    M      N      Rem

initial      M      N      M%N

1 iteration  N     M%N    N%(M%N)

2 iterations M%N  N%(M%N) (M%N)%(N%(M%N)) < (M%N)/2

Tak więc po dwóch iteracjach reszta to co najwyżej połowa pierwotnej wartości. To by pokazało, że liczba iteracji wynosi co najwyżej2logN = O(logN) .

Zauważ, że algorytm oblicza Gcd (M, N), zakładając M> = N. (Jeśli N> M, pierwsza iteracja pętli zamienia je).


2

Twierdzenie Gabriela Lame'a ogranicza liczbę kroków przez log (1 / sqrt (5) * (a + 1/2)) - 2, gdzie podstawą logu jest (1 + sqrt (5)) / 2. Dotyczy to najgorszego scenariusza dla algorytmu i występuje, gdy wejściami są kolejne liczby Fibanocciego.

Nieco bardziej liberalne ograniczenie to: log a, gdzie podstawą logu jest (sqrt (2)) wynika z Koblitz.

Do celów kryptograficznych zwykle bierzemy pod uwagę złożoność bitową algorytmów, biorąc pod uwagę, że rozmiar bitu jest określony w przybliżeniu przez k = loga.

Oto szczegółowa analiza złożoności bitowej algorytmu Euclid:

Chociaż w większości odniesień bitowa złożoność algorytmu Euclid jest określona przez O (loga) ^ 3, istnieje ściślejsza granica, która jest O (loga) ^ 2.

Rozważać; r0 = a, r1 = b, r0 = q1. r1 + r2. . . , ri-1 = qi.ri + ri + 1,. . . , rm-2 = qm-1.rm-1 + rm rm-1 = qm.rm

zauważ, że: a = r0> = b = r1> r2> r3 ...> rm-1> rm> 0 .......... (1)

a rm jest największym wspólnym dzielnikiem a i b.

Stwierdzeniem w książce Koblitza (Kurs teorii liczb i kryptografii) można udowodnić, że: ri + 1 <(ri-1) / 2 ................. ( 2)

Ponownie w Koblitz liczba operacji bitowych wymaganych do podzielenia k-bitowej liczby całkowitej dodatniej przez l-bitową liczbę całkowitą dodatnią (zakładając k> = l) jest podana jako: (k-l + 1). L ...... ............. (3)

Przy (1) i (2) liczba podziałów wynosi O (loga), a więc przy (3) całkowita złożoność wynosi O (loga) ^ 3.

Teraz można to zredukować do O (loga) ^ 2 przez uwagę w Koblitz.

rozważ ki = logri +1

przez (1) i (2) mamy: ki + 1 <= ki dla i = 0,1, ..., m-2, m-1 i ki + 2 <= (ki) -1 dla i = 0 , 1, ..., m-2

a przez (3) całkowity koszt m działek jest ograniczony przez: SUMA [(ki-1) - ((ki) -1))] * ki dla i = 0,1,2, .., m

przekształcając to: SUMA [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2

Więc bitowa złożoność Algorytmu Euklidesa wynosi O (loga) ^ 2.


1

Jednak dla algorytmu iteracyjnego mamy:

int iterativeEGCD(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a % n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

W przypadku par Fibonacciego nie ma różnicy między iterativeEGCD()i iterativeEGCDForWorstCase()gdzie to ostatnie wygląda następująco:

int iterativeEGCDForWorstCase(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a - n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

Tak, z parami Fibonacciego n = a % ni n = a - nto jest dokładnie to samo.

Wiemy również, że we wcześniejszej odpowiedzi na to samo pytanie, jest tam panujące czynnikiem zmniejszającym: factor = m / (n % m).

Dlatego, aby ukształtować iteracyjną wersję euklidesowego GCD w zdefiniowanej formie, możemy przedstawić jako „symulator” w następujący sposób:

void iterativeGCDSimulator(long long x, long long y) {
    long long i;
    double factor = x / (double)(x % y);
    int numberOfIterations = 0;
    for ( i = x * y ; i >= 1 ; i = i / factor) {
        numberOfIterations ++;
    }
    printf("\nIterative GCD Simulator iterated %d times.", numberOfIterations);
}

Opierając się na pracy (ostatni slajd) dr Jauhar Ali, powyższa pętla jest logarytmiczna.

wprowadź opis obrazu tutaj

Tak, mały Oh, ponieważ symulator mówi co najwyżej liczbę iteracji . Pary inne niż Fibonacciego wymagałyby mniejszej liczby iteracji niż Fibonacci, gdy są badane na Euklidesowym GCD.


Ponieważ badanie przeprowadzono w języku C, problemy z precyzją mogą dawać błędne / nieprecyzyjne wartości. Dlatego użyto long long , aby lepiej dopasować zmiennoprzecinkową zmienną o nazwie factor . Użyty kompilator to MinGW 2.95.
Mohamed Ennahdi El Idrissi

1

Na każdym kroku są dwa przypadki

b> = a / 2, a następnie a, b = b, a% b da b co najwyżej połowę swojej poprzedniej wartości

b <a / 2, to a, b = b, a% b będzie stanowić co najwyżej połowę swojej poprzedniej wartości, ponieważ b jest mniejsze niż a / 2

Tak więc na każdym kroku algorytm zmniejszy co najmniej jedną liczbę do co najmniej połowy mniej.

W co najwyżej kroku O (log a) + O (log b) zostanie to zredukowane do prostych przypadków. Co daje algorytm O (log n), gdzie n jest górną granicą a i b.

Znalazłem to tutaj

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.