Complexidade de tempo do Algoritmo de Euclides

Estou tendo dificuldade em decidir qual é a complexidade de tempo do algoritmo do maior denominador comum de Euclides. Este algoritmo em pseudocódigo é:

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

Parece depender de a e b . Meu pensamento é que a complexidade do tempo é O (a% b). Isso é correto? Existe uma maneira melhor de escrever isso?

Um truque para analisar a complexidade do tempo do algoritmo de Euclides é seguir o que acontece em duas iterações:

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

Agora, aeb diminuirão, em vez de apenas um, o que torna a análise mais fácil. Você pode dividi-lo em casos:

• Tiny A: 2a <= b
• Tiny B: 2b <= a
• A pequeno: 2a > bmasa < b
• B pequeno: 2b > amasb < a
• Igual: a == b

Agora vamos mostrar que cada caso diminui o total a+bem pelo menos um quarto:

• Tiny A: b % (a % b) < ae 2a <= b, portanto, bé diminuído em pelo menos metade, então a+bdiminuído em pelo menos25%
• Tiny B: a % b < be 2b <= a, portanto, aé diminuído em pelo menos metade, então a+bdiminuído em pelo menos25%
• A pequeno: bse tornará b-a, que é menor que b/2, diminuindo a+bpelo menos 25%.
• B pequeno: ase tornará a-b, que é menor do que a/2, diminuindo a+bpelo menos 25%.
• Igual: a+bcai para 0, que obviamente está diminuindo a+bpelo menos 25%.

Portanto, por análise de caso, cada passo duplo diminui a+bpelo menos 25%. Há um número máximo de vezes que isso pode acontecer antes de a+bser forçado a cair para baixo 1. O número total de etapas ( S) até atingirmos 0 deve ser satisfeito (4/3)^S <= A+B. Agora é só trabalhar:

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

Portanto, o número de iterações é linear no número de dígitos de entrada. Para números que cabem em registradores de cpu, é razoável modelar as iterações como tendo um tempo constante e fingir que o tempo total de execução do mdc é linear.

Obviamente, se você estiver lidando com números inteiros grandes, deve levar em consideração o fato de que as operações de módulo em cada iteração não têm um custo constante. A grosso modo, o tempo de execução assintótico total será n ^ 2 vezes um fator polilogarítmico. Algo parecido n^2 lg(n) 2^O(log* n) . O fator polilogarítmico pode ser evitado usando um gcd binário .

A maneira adequada de analisar um algoritmo é determinar seus piores cenários. O pior caso de GCD euclidiano ocorre quando pares de Fibonacci estão envolvidos. void EGCD(fib[i], fib[i - 1]), onde i> 0.

Por exemplo, vamos optar pelo caso em que o dividendo é 55 e o divisor é 34 (lembre-se de que ainda estamos lidando com números de Fibonacci).

Como você pode notar, esta operação custou 8 iterações (ou chamadas recursivas).

Vamos tentar números de Fibonacci maiores, a saber, 121393 e 75025. Podemos notar aqui também que foram necessárias 24 iterações (ou chamadas recursivas).

Você também pode notar que cada iteração produz um número de Fibonacci. É por isso que temos tantas operações. Não podemos obter resultados semelhantes apenas com números de Fibonacci, de fato.

Portanto, a complexidade do tempo será representada por um pequeno Oh (limite superior), desta vez. O limite inferior é intuitivamente Omega (1): caso de 500 dividido por 2, por exemplo.

Vamos resolver a relação de recorrência:

Podemos dizer então que o GCD Euclidiano pode fazer operação log (xy) no máximo .

Há uma ótima visão disso no artigo da wikipedia .

Ele ainda tem um bom gráfico de complexidade para pares de valores.

Não é O(a%b) .

É sabido (ver artigo) que nunca dará mais passos do que cinco vezes o número de dígitos do número menor. Portanto, o número máximo de etapas cresce conforme o número de dígitos (ln b). O custo de cada etapa também cresce conforme o número de dígitos, portanto, a complexidade é limitada por O(ln^2 b)onde b é o número menor. Esse é um limite superior e o tempo real geralmente é menor.

Veja aqui .

Em particular esta parte:

Lamé mostrou que o número de passos necessários para chegar ao máximo divisor comum para dois números menores que n é

Portanto, O(log min(a, b))é um bom limite superior.

Aqui está uma compreensão intuitiva da complexidade do tempo de execução do algoritmo de Euclid. As provas formais são abordadas em vários textos, como Introdução a Algoritmos e TAOCP Vol 2.

Primeiro pense no que aconteceria se tentássemos calcular o mdc de dois números de Fibonacci F (k + 1) e F (k). Você pode observar rapidamente que o algoritmo de Euclides itera em F (k) e F (k-1). Ou seja, com cada iteração, descemos um número na série de Fibonacci. Como os números de Fibonacci são O (Phi ^ k) onde Phi é a razão áurea, podemos ver que o tempo de execução do GCD foi O (log n) onde n = max (a, b) e log tem base de Phi. A seguir, podemos provar que este seria o pior caso observando que os números de Fibonacci consistentemente produzem pares onde os restantes permanecem grandes o suficiente em cada iteração e nunca se tornam zero até que você tenha chegado ao início da série.

Podemos fazer O (log n) onde n = max (a, b) limitado ainda mais. Suponha que b> = a para que possamos escrever limitado em O (log b). Primeiro, observe que GCD (ka, kb) = GCD (a, b). Como os maiores valores de k são mdc (a, c), podemos substituir b por b / mdc (a, b) em nosso tempo de execução levando a um limite mais estreito de O (log b / mdc (a, b)).

O pior caso do Algoritmo de Euclides é quando os remanescentes são os maiores possíveis em cada etapa, ou seja. por dois mandatos consecutivos da sequência de Fibonacci.

Quando n e m são o número de dígitos de aeb, assumindo n> = m, o algoritmo usa divisões O (m).

Observe que as complexidades são sempre fornecidas em termos dos tamanhos das entradas, neste caso o número de dígitos.

O pior caso surgirá quando n e m forem números consecutivos de Fibonacci.

mdc (Fn, Fn − 1) = mdc (Fn − 1, Fn − 2) = ⋯ = mdc (F1, F0) = 1 enésimo número de Fibonacci é 1,618 ^ n, onde 1,618 é a proporção áurea.

Portanto, para encontrar mdc (n, m), o número de chamadas recursivas será Θ (logn).

Aqui está a análise no livro Data Structures and Algorithm Analysis in C, de Mark Allen Weiss (segunda edição, 2.4.4):

O algoritmo de Euclides funciona calculando continuamente os restos até que 0 seja alcançado. O último resto diferente de zero é a resposta.

Aqui está o código:

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

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

Aqui está um TEOREMA que vamos usar:

Se M> N, então M mod N <M / 2.

PROVA:

Existem dois casos. Se N <= M / 2, então, como o resto é menor que N, o teorema é verdadeiro para este caso. O outro caso é N> M / 2. Mas então N vai para M uma vez com um resto M - N <M / 2, provando o teorema.

Portanto, podemos fazer a seguinte inferência:

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

Portanto, após duas iterações, o restante é no máximo metade de seu valor original. Isso mostraria que o número de iterações é no máximo 2logN = O(logN).

Observe que o algoritmo calcula Gcd (M, N), assumindo M> = N. (Se N> M, a primeira iteração do loop os troca.)

O Teorema de Gabriel Lame limita o número de passos por log (1 / sqrt (5) * (a + 1/2)) - 2, onde a base do log é (1 + sqrt (5)) / 2. Este é o pior cenário para o algoritmo e ocorre quando as entradas são números de Fibanocci consecutivos.

Um limite ligeiramente mais liberal é: log a, onde a base do log é (sqrt (2)) é implícito por Koblitz.

Para fins criptográficos, normalmente consideramos a complexidade bit a bit dos algoritmos, levando em consideração que o tamanho do bit é dado aproximadamente por k = loga.

Aqui está uma análise detalhada da complexidade bit a bit do Algorito de Euclides:

Embora na maioria das referências a complexidade bit a bit do Algoritmo de Euclides seja dada por O (loga) ^ 3, existe um limite mais estreito que é O (loga) ^ 2.

Considerar; 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

observe que: a = r0> = b = r1> r2> r3 ...> rm-1> rm> 0 .......... (1)

e rm é o máximo divisor comum de a e b.

Por uma reivindicação no livro de Koblitz (Um curso em Teoria e Criptografia dos números) pode ser provado que: ri + 1 <(ri-1) / 2 ................. ( 2)

Novamente em Koblitz, o número de operações de bits necessárias para dividir um inteiro positivo de k-bit por um inteiro positivo de l-bit (assumindo k> = l) é dado como: (k-l + 1) .l ...... ............. (3)

Por (1) e (2) o número de divisões é O (loga) e então por (3) a complexidade total é O (loga) ^ 3.

Agora, isso pode ser reduzido a O (loga) ^ 2 por uma observação em Koblitz.

considere ki = logri +1

por (1) e (2) temos: ki + 1 <= ki para i = 0,1, ..., m-2, m-1 e ki + 2 <= (ki) -1 para i = 0 , 1, ..., m-2

e por (3) o custo total das m divisões é limitado por: SUM [(ki-1) - ((ki) -1))] * ki para i = 0,1,2, .., m

reorganizando isso: SUM [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2

Portanto, a complexidade bit a bit do Algoritmo de Euclides é O (loga) ^ 2.

Para o algoritmo iterativo, entretanto, temos:

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;
}

Com os pares de Fibonacci, não há diferença entre iterativeEGCD()e iterativeEGCDForWorstCase()onde o último se parece com o seguinte:

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;
}

Sim, com pares de Fibonacci, n = a % nen = a - n é exatamente a mesma coisa.

Também sabemos que, em uma resposta anterior para a mesma pergunta, existe um fator decrescente predominante: factor = m / (n % m) .

Portanto, para modelar a versão iterativa do GCD Euclidiano de uma forma definida, podemos representar como um "simulador" assim:

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);
}

Com base no trabalho (último slide) do Dr. Jauhar Ali, o loop acima é logarítmico.

Sim, pequeno Oh porque o simulador informa o número de iterações no máximo . Os pares não Fibonacci levariam um número menor de iterações do que Fibonacci, quando testados no GCD Euclidiano.

Em cada etapa, existem dois casos

b> = a / 2, então a, b = b, a% b fará b no máximo a metade de seu valor anterior

b <a / 2, então a, b = b, a% b fará a no máximo a metade de seu valor anterior, já que b é menor que a / 2

Portanto, a cada etapa, o algoritmo reduzirá pelo menos um número para pelo menos metade menos.

Em no máximo O (log a) + O (log b) passo, isso será reduzido aos casos simples. Que produz um algoritmo O (log n), onde n é o limite superior de a e b.

eu encontrei aqui