Euclidean Algorithm的时间复杂度

Euclidean Algorithm就是GCD,求最大公约数的,大概代码如下:
递归:

// a > b
int gcd(int a, int b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

非递归:

// a > b
int gcd(int a, int b){
    int tmp;
    while(b){
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

究竟求一次gcd需要多少次递归呢?时间复杂度?

先考虑一个引理:
For positive integers p and q with p > q ==> (p mod q) < p/2 证明就是: 1. q < p/2,因为p mod q一定比q小,所以也小于p/2 2. q >= p/2,这个时候p mod q其实就是p-q,显然小于p/2

有这个引理就好办了:

对于如下gcd过程:
gcd(a, b)
—gcd(b, a mod b) ==> gcd(b, c)
——gcd(c, b mod c) ==> gcd(c, d)

在最后一个过程中,d = b mod c,所以有 d < b/2 这样我们可以归纳出,在经过两步以后,gcd函数的第二个参数会变成原来的1/2,显然这是一个log的时间复杂度 所以Euclidean Algorithm: gcd(a, b)的时间复杂度是O(log b),证毕。

Tags : , ,

0 thoughts on “Euclidean Algorithm的时间复杂度”

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Click the right image To submit your comment: