Algoritmos MatemáticosIntermediate

Algoritmo Euclídeo Extendido

Extiende el algoritmo euclídeo para encontrar enteros x e y que satisfacen la identidad de Bézout: ax + by = MCD(a, b). No solo calcula el MCD sino que también encuentra los coeficientes de combinaciones lineales. Fundamental para aritmética modular, criptografía RSA y resolución de ecuaciones diofánticas lineales.

#mathematical#number-theory#cryptography#modular-arithmetic

Complexity Analysis

Time (Average)

O(log min(a, b))

Expected case performance

Space

O(1)

Memory requirements

Time (Best)

O(log min(a, b))

Best case performance

Time (Worst)

O(log min(a, b))

Worst case performance

Input Numbers (positive integers)

Number A

Number B

Quick Presets:

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Algoritmos Matemáticos

Criba de Eratóstenes

Beginner

Encuentra todos los números primos hasta n marcando iterativamente los compuestos. Nombrado en honor a Eratóstenes de Cirene (c. 276-194 a.C.).

O(n log log n)

O(n)

mathematicalprime-numbers

Start Learning

Triángulo de Pascal

Beginner

Arreglo triangular de coeficientes binomiales donde cada número es la suma de los dos números directamente encima de él. Nombrado en honor a Blaise Pascal (1623-1662), aunque conocido por matemáticos siglos antes. Demuestra hermosos patrones matemáticos incluyendo expansión binomial, combinatoria y conexiones con los números de Fibonacci.

O(n²)

mathematicalcombinatorics

Start Learning

Algoritmo Euclídeo (MCD)

Beginner

Algoritmo antiguo de alrededor del 300 a.C. que calcula eficientemente el máximo común divisor de dos enteros. Basado en el principio de que MCD(a, b) = MCD(b, a mod b). Uno de los algoritmos más antiguos en uso continuo, formando la base de la teoría de números, criptografía y simplificación de fracciones.

O(log min(a, b))

O(1)

mathematicalnumber-theory

Start Learning

Back to Algoritmos Matemáticos