Toán học

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 4)

Toán học

Extended Euclidean Algorithm

Thời gian (Time) O(log min(a, b))
Không gian (Space) O(1)

Mô tả nguyên lý

Tìm ước chung lớn nhất đồng thời tính các hệ số x, y sao cho ax + by = gcd.

Cài đặt mẫu (Implementation)

function extendedGCD($a, $b, &$x, &$y) {
    if ($a == 0) { $x = 0; $y = 1; return $b; }
    $x1 = 1; $y1 = 1;
    $gcd = extendedGCD($b % $a, $a, $x1, $y1);
    $x = $y1 - floor($b / $a) * $x1;
    $y = $x1;
    return $gcd;
}
Toán học

Matrix Exponentiation

Thời gian (Time) O(k^3 log n)
Không gian (Space) O(k^2)

Mô tả nguyên lý

Tính lũy thừa ma trận lớn trong thời gian logarithmic.

Cài đặt mẫu (Implementation)

// Nhân ma trận nhị phân kết hợp lũy thừa chia đôi số mũ.
Toán học

Miller-Rabin Primality Test

Thời gian (Time) O(k log^3 n)
Không gian (Space) O(1)

Mô tả nguyên lý

Thuật toán kiểm tra tính nguyên tố probabilistic cho số rất lớn.

Cài đặt mẫu (Implementation)

// Sử dụng kiểm tra tính đồng dư xác suất qua nhiều cơ sở khác nhau.
Toán học

Pollard Rho Algorithm

Thời gian (Time) O(n^(1/4))
Không gian (Space) O(1)

Mô tả nguyên lý

Thuật toán phân tích thừa số nguyên tố ngẫu nhiên cực nhanh.

Cài đặt mẫu (Implementation)

// Sử dụng chu kỳ sinh số giả ngẫu nhiên kết hợp thuật toán Floyd.