LCM 프로그램의 복잡성은 무엇입니까?

가변 숫자의 LCM을 찾는 프로그램은 다음과 같습니다.LCM 프로그램의 복잡성은 무엇입니까?

전 용

: 난 3,9,13의 LCM을 찾을 수 있다면 그때는 다음과 같이 실행한다 : LCM을 (1,3) LCM (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; 


}

출처

2014-05-10 svetaketu

귀하의 사례에서 'n'은 무엇입니까? Btw. 'lcm (1, x) = x' 이후 첫 번째''lcm'을 버림으로써 최적화 할 수 있습니다. – Henry

n은 lcm을 찾을 수있는 총 숫자입니다. – svetaketu

'x % 0'은 무엇입니까? 돌아온 후 휴식 시간은 어디에서 끝나나요? 어쨌든, 시퀀스에 다른 알고리즘을 반복적으로 적용하여 구성된 알고리즘을 가지고 있다면 복잡도는 시퀀스의 길이에 서브 알고리즘의 복잡도를 곱한 값입니다. 스포일러를 제공하지 않기 위해 나머지는 맡길 것입니다. –

(도 LCM 방법의 복잡성)하여 gcd 방법의 복잡성은 n이 O 인 max(x, y) (N)이다. 왜냐하면 최악의 경우 x와 y는 비례 적이기 때문에 n이 1로 감소해야 함을 의미합니다. 유클리드의 GCD 알고리즘은 더 빠릅니다. http://en.wikipedia.org/wiki/Euclidean_algorithm

출처

2014-05-10 06:44:40 Duncan

괜찮아요.하지만 그것을 얻을 수 있다고 생각하지만, 5cm 숫자의 lcm을 찾아야 만합니다. main에서 for 루프는 lcm 함수를 N = 5 번 호출합니다. 그래서 전체 프로그램의 복잡성은 O입니다. (N * n) 여기서 n = max (x, y)? – svetaketu

단일 테스트 케이스를 조정하면 O (n) 복잡합니다.

이유

LCM을 계산하는 경우는 * B/GCD (a, b) 상기 통화 GCD (a가, b) GCD에

(a가, b) 함수 간단한 반면을 호출 루프는 값이 1 씩 감소함에 따라 양수로부터 완벽하게 나눌 수있게 될 때까지 작은 수로 더 큰 수의 법율을 수행했습니다. 그래서 O n은 작은 하나 둘 사이의 숫자입니다 (N)이다

당신은 당신은 같이 진행할 수

출처

2014-05-10 06:44:56

는 O를 가지고 각 테스트 케이스 (N)에 대한 다음 테스트 케이스의 수와 실행 다음 :

enter image description here

출처

2014-05-11 05:29:23

LCM 프로그램의 복잡성은 무엇입니까?

답변

관련 문제