c - 我的 LCM 程序的复杂性是多少？

Question

下面给出的是一个求可变数量数字的最小公倍数的程序。

例如:如果我必须找到 3,9,13 的 lcm 那么它执行如下: 长厘米(1,3) 长厘米(3,9) lcm(9,13)

我只想知道这个程序的复杂性是多少。是 O(n) 还是 O(n^2)。你能告诉我为什么会这样吗？

#include <stdio.h>

int gcd(int x,int y)
{
    int n;
    if(x>y)
        n=y;
    else
        n=x;

    while(n>=0){
        if(x%n==0 && y%n==0){
            return n;
            break;
        }
        n--;
}
    return 1;
}

int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}

int main()
{
    int tot,i,l=1;
    int n[10];
    printf("Enter the total numbers:");
    scanf("%d",&tot);
    if(tot>10 || tot<2){
        printf("Sorry invalid inputs");
        return 1;
    }

    printf("Enter the numbers one by one:");
    for(i=0;i<tot;i++)
        scanf("%d",&n[i]);

    for(i=0;i<tot;i++){
        l=lcm(l,n[i]);
    }

    printf("The LCM is %d",l);
    return 0;


}

Answer 1

gcd 方法的复杂度(也是 lcm 方法的复杂度)为 O(n)，其中 n 为 max(x, y)。这是因为在最坏的情况下 x 和 y 互质，这意味着 n 必须递减到 1。Euclid 的 GCD 算法更快:http://en.wikipedia.org/wiki/Euclidean_algorithm