Złożoność czasowa algorytmu Euklidesa

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ć?

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 .

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).

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).

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:

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

Ś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.

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

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

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)).

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.

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).

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).

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.

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.

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.

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