Kompleksitas waktu dari Algoritma Euclid

Saya mengalami kesulitan dalam menentukan kompleksitas waktu dari algoritma penyebut umum terbesar Euclid. Algoritma dalam pseudo-code ini adalah:

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

Sepertinya tergantung pada a dan b . Pemikiran saya adalah bahwa kompleksitas waktu adalah O (a% b). Apakah itu benar? Apakah ada cara yang lebih baik untuk menulisnya?

Salah satu trik untuk menganalisis kompleksitas waktu algoritma Euclid adalah mengikuti apa yang terjadi pada dua iterasi:

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

Sekarang a dan b keduanya akan berkurang, bukan hanya satu, yang membuat analisis lebih mudah. Anda dapat membaginya menjadi beberapa kasus:

• Tiny A: 2a <= b
• Kecil B: 2b <= a
• Kecil A: 2a > btapia < b
• Kecil B: 2b > atapib < a
• Sama: a == b

Sekarang kami akan menunjukkan bahwa setiap kasus mengurangi total a+bsetidaknya seperempat:

• Tiny A: b % (a % b) < adan 2a <= b, jadi bberkurang setidaknya setengahnya, jadi a+bberkurang setidaknya25%
• Tiny B: a % b < bdan 2b <= a, begitu ajuga berkurang setidaknya setengah, jadi a+bberkurang setidaknya25%
• Kecil A: bakan menjadi b-a, yang kurang dari b/2, berkurang a+bsetidaknya 25%.
• Kecil B: aakan menjadi a-b, yang kurang dari a/2, berkurang a+bsetidaknya 25%.
• Sama: a+bturun ke 0, yang jelas menurun a+bsetidaknya 25%.

Oleh karena itu, dengan analisis kasus, setiap langkah ganda berkurang a+bsetidaknya 25%. Ada beberapa kali hal ini dapat terjadi maksimal sebelum a+bdipaksa untuk turun di bawah 1. Jumlah langkah ( S) sampai kita mencapai 0 harus memuaskan (4/3)^S <= A+B. Sekarang kerjakan saja:

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

Jadi jumlah iterasi linier dalam jumlah digit input. Untuk bilangan yang cocok dengan register cpu, masuk akal untuk memodelkan iterasi sebagai waktu yang konstan dan menganggap bahwa total waktu berjalan dari gcd adalah linier.

Tentu saja, jika Anda berurusan dengan bilangan bulat besar, Anda harus memperhitungkan fakta bahwa operasi modulus dalam setiap iterasi tidak memiliki biaya tetap. Secara kasar, total waktu proses asimtotik akan menjadi n ^ 2 kali faktor polilogaritmik. Sesuatu seperti n^2 lg(n) 2^O(log* n) . Faktor polilogaritmik dapat dihindari dengan menggunakan gcd biner .

Cara yang sesuai untuk menganalisis suatu algoritma adalah dengan menentukan skenario kasus terburuknya. Kasus terburuk GCD Euclidean terjadi ketika Fibonacci Pairs terlibat. void EGCD(fib[i], fib[i - 1]), di mana i> 0.

Sebagai contoh, mari kita memilih kasus di mana pembagi adalah 55, dan pembaginya adalah 34 (ingat bahwa kita masih berurusan dengan bilangan fibonacci).

Seperti yang mungkin Anda perhatikan, operasi ini menghabiskan 8 iterasi (atau panggilan rekursif).

Mari kita coba bilangan Fibonacci yang lebih besar, yaitu 121393 dan 75025. Kita juga dapat melihat di sini bahwa dibutuhkan 24 iterasi (atau panggilan rekursif).

Anda juga dapat melihat bahwa setiap iterasi menghasilkan angka Fibonacci. Itulah mengapa kami memiliki begitu banyak operasi. Kami tidak dapat memperoleh hasil yang serupa hanya dengan angka Fibonacci.

Oleh karena itu, kompleksitas waktu akan diwakili oleh Oh kecil (batas atas), kali ini. Batas bawahnya adalah Omega (1) secara intuitif: kasus 500 dibagi 2, misalnya.

Mari selesaikan hubungan pengulangan:

Kita dapat mengatakan bahwa GCD Euclidean dapat membuat operasi log (xy) paling banyak .

Ini bagus sekali di artikel wikipedia .

Ia bahkan memiliki plot kompleksitas yang bagus untuk pasangan nilai.

Tidak O(a%b).

Diketahui (lihat artikel) bahwa tidak akan pernah lebih dari lima kali jumlah digit dalam bilangan yang lebih kecil. Jadi jumlah langkah maksimal bertambah seiring dengan jumlah digit (ln b). Biaya setiap langkah juga bertambah seiring banyaknya digit, sehingga kompleksitasnya dibatasi oleh O(ln^2 b)b adalah bilangan yang lebih kecil. Itu adalah batas atas, dan waktu sebenarnya biasanya lebih singkat.

Lihat disini .

Khususnya bagian ini:

Lamé menunjukkan bahwa jumlah anak tangga yang diperlukan untuk sampai pada pembagi persekutuan terbesar untuk dua bilangan kurang dari n adalah

Begitu O(log min(a, b))juga batas atas yang bagus.

Berikut pemahaman intuitif tentang kompleksitas runtime dari algoritma Euclid. Bukti formal tercakup dalam berbagai teks seperti Pengantar Algoritma dan TAOCP Vol 2.

Pertama pikirkan tentang bagaimana jika kita mencoba mengambil gcd dari dua bilangan Fibonacci F (k + 1) dan F (k). Anda mungkin dengan cepat mengamati bahwa algoritma Euclid melakukan iterasi ke F (k) dan F (k-1). Artinya, dengan setiap iterasi kita turun satu angka dalam deret Fibonacci. Karena bilangan Fibonacci adalah O (Phi ^ k) di mana Phi adalah rasio emas, kita dapat melihat bahwa runtime GCD adalah O (log n) di mana n = max (a, b) dan log memiliki basis Phi. Selanjutnya, kita dapat membuktikan bahwa ini akan menjadi kasus terburuk dengan mengamati bahwa bilangan Fibonacci secara konsisten menghasilkan pasangan di mana sisanya tetap cukup besar di setiap iterasi dan tidak pernah menjadi nol hingga Anda tiba di awal rangkaian.

Kita bisa membuat O (log n) di mana n = max (a, b) terikat lebih erat lagi. Asumsikan b> = a sehingga kita dapat menulis terikat pada O (log b). Pertama, perhatikan bahwa PBT (ka, kb) = PBT (a, b). Karena nilai terbesar k adalah gcd (a, c), kita dapat mengganti b dengan b / gcd (a, b) dalam runtime kita yang mengarah ke batas O yang lebih ketat (log b / gcd (a, b)).

Kasus terburuk dari Algoritma Euclid adalah ketika sisanya adalah yang terbesar di setiap langkah, yaitu. untuk dua suku berturut-turut dari deret Fibonacci.

Jika n dan m adalah jumlah digit a dan b, dengan asumsi n> = m, algoritme menggunakan pembagian O (m).

Perhatikan bahwa kompleksitas selalu diberikan dalam hal ukuran input, dalam hal ini jumlah digit.

Kasus terburuk akan muncul jika n dan m adalah bilangan Fibonacci yang berurutan.

gcd (Fn, Fn − 1) = gcd (Fn − 1, Fn − 2) = ⋯ = gcd (F1, F0) = 1 dan angka Fibonacci ke-n adalah 1.618 ^ n, di mana 1.618 adalah rasio Emas.

Jadi, untuk mencari gcd (n, m), jumlah panggilan rekursif akan menjadi Θ (logn).

Berikut adalah analisis dalam buku Struktur Data dan Analisis Algoritma di C oleh Mark Allen Weiss (edisi kedua, 2.4.4):

Algoritme Euclid bekerja dengan terus menghitung sisa hingga tercapai 0. Sisa bukan nol terakhir adalah jawabannya.

Ini kodenya:

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

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

Berikut adalah TEORI yang akan kita gunakan:

Jika M> N, maka M mod N <M / 2.

BUKTI:

Ada dua kasus. Jika N <= M / 2, maka karena sisanya lebih kecil dari N, teorema benar untuk kasus ini. Kasus lainnya adalah N> M / 2. Tapi kemudian N pergi ke M sekali dengan sisa M - N <M / 2, membuktikan teorema tersebut.

Jadi, kita bisa membuat kesimpulan berikut:

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

Jadi, setelah dua iterasi, sisanya paling banyak setengah dari nilai aslinya. Ini akan menunjukkan bahwa jumlah iterasi paling banyak 2logN = O(logN).

Perhatikan bahwa, algoritme menghitung Gcd (M, N), dengan asumsi M> = N. (Jika N> M, iterasi pertama loop menukar mereka.)

Teorema Gabriel Lame membatasi jumlah langkah dengan log (1 / akar persegi (5) * (a + 1/2)) - 2, di mana basis lognya adalah (1 + akar persegi (5)) / 2. Ini untuk skenario kasus terburuk untuk algoritme dan ini terjadi ketika input adalah angka Fibanocci yang berurutan.

Batas yang sedikit lebih liberal adalah: log a, di mana basis log adalah (akar (2)) disiratkan oleh Koblitz.

Untuk tujuan kriptografi, kami biasanya mempertimbangkan kompleksitas bitwise dari algoritme, dengan mempertimbangkan bahwa ukuran bit diberikan kira-kira oleh k = loga.

Berikut adalah analisis rinci kompleksitas bitwise dari Algoritma Euclid:

Meskipun dalam kebanyakan referensi kompleksitas bitwise dari Algoritma Euclid diberikan oleh O (loga) ^ 3 ada batas yang lebih ketat yaitu O (loga) ^ 2.

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

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

dan rm adalah pembagi persekutuan terbesar dari a dan b.

Dengan Klaim dalam buku Koblitz (Mata kuliah Teori Bilangan dan Kriptografi) dapat dibuktikan bahwa: ri + 1 <(ri-1) / 2 ................. ( 2)

Sekali lagi di Koblitz jumlah operasi bit yang diperlukan untuk membagi bilangan bulat positif k-bit dengan bilangan bulat positif l-bit (dengan asumsi k> = l) diberikan sebagai: (k-l + 1). L ...... ............. (3)

Dengan (1) dan (2) jumlah divisi adalah O (loga) dan oleh (3) total kompleksitasnya adalah O (loga) ^ 3.

Sekarang ini dapat direduksi menjadi O (loga) ^ 2 dengan komentar di Koblitz.

pertimbangkan ki = logri +1

oleh (1) dan (2) kami memiliki: ki + 1 <= ki untuk i = 0,1, ..., m-2, m-1 dan ki + 2 <= (ki) -1 untuk i = 0 , 1, ..., m-2

dan dengan (3) total biaya dari m divisi dibatasi oleh: SUM [(ki-1) - ((ki) -1))] * ki untuk i = 0,1,2, .., m

menyusun ulang ini: SUM [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2

Jadi kompleksitas bitwise Algoritma Euclid adalah O (loga) ^ 2.

Namun, untuk algoritme iteratif, kami memiliki:

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

Dengan pasangan Fibonacci, tidak ada perbedaan antara iterativeEGCD()dan di iterativeEGCDForWorstCase()mana yang terakhir terlihat seperti berikut:

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

Ya, dengan Pasangan Fibonacci, n = a % ndan n = a - nitu adalah hal yang persis sama.

Kita juga tahu bahwa, dalam respon awal untuk pertanyaan yang sama, ada faktor penurunan yang berlaku: factor = m / (n % m).

Oleh karena itu, untuk membentuk versi iteratif GCD Euclidean dalam bentuk yang ditentukan, kami dapat menggambarkannya sebagai "simulator" seperti ini:

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

Berdasarkan karya (slide terakhir) Dr. Jauhar Ali, loop di atas adalah logaritmik.

Ya, Oh kecil karena simulator memberi tahu jumlah iterasi paling banyak . Pasangan non-Fibonacci akan membutuhkan jumlah iterasi yang lebih sedikit daripada Fibonacci, ketika diperiksa di Euclidean GCD.

Di setiap langkah, ada dua kasus

b> = a / 2, maka a, b = b, a% b akan membuat b paling banyak setengah dari nilai sebelumnya

b <a / 2, maka a, b = b, a% b akan menghasilkan paling banyak setengah dari nilai sebelumnya, karena b kurang dari a / 2

Jadi di setiap langkah, algoritme akan mengurangi setidaknya satu angka menjadi setidaknya setengahnya.

Di paling banyak langkah O (log a) + O (log b) , ini akan direduksi menjadi kasus sederhana. Yang menghasilkan algoritma O (log n), dimana n adalah batas atas dari a dan b.

Saya telah menemukannya di sini