인프런 커뮤니티 질문&답변

안녕하세요, 2scent님!

말씀하신대로 정확한 시간 복잡도는 O(√a + √b)라고 할 수 있습니다. 하지만, 시간 복잡도를 표기할 때는 보통 상수배가 크지 않은 경우는 생략할 수 있기 때문에 O(√max(a, b))로 표기하였습니다.

√max(a, b) <= √a + √b <= 2√max(a, b) 이므로

또 궁금하신 점 있으시면 질문해주세요. :)

안녕하세요, 인프런 AI 인턴입니다.

2scent님께서 질문하신 최대 공약수(GCD)를 구하는 시간 복잡도에 대한 부분은 유클리드 호제법(Euclidean algorithm)을 사용하면 O(log(min(a, b)))의 시간 복잡도를 가지게 됩니다. 따라서 말씀하신 O(√a + √b)의 시간 복잡도는 일반적인 방법으로 최대 공약수를 구할 때가 아니라, 유클리드 호제법을 사용하는 경우 그러한 복잡도가 적용됩니다.

유클리드 호제법은 a와 b의 나머지를 이용하여 반복적으로 최대 공약수를 계산하는 방법입니다. 이 알고리즘은 a % b의 결과를 이용하여 반복적으로 b, a % b에 대해 계산을 진행하고, b가 0이 될 때 a를 최대 공약수로 반환합니다. 이 과정은 a와 b의 크기에 따라 log 단계로 줄어들면서 최적화하는 방식으로 작동합니다.

다음은 유클리드 호제법의 동작 방식에 대한 예시입니다:

1. gcd(a, b)는 gcd(b, a % b)로 변환됩니다.
   
2. 이 과정을 b가 0이 될 때까지 반복합니다.
   
3. 최종적으로 a가 최대 공약수가 됩니다.
   

따라서 유클리드 호제법을 사용하면 두 수 각각의 약수를 모두 찾지 않으므로 시간 복잡도가 O(log(min(a, b)))가 되고, 이는 매우 효율적임을 보여줍니다.

관련된 설명을 참고하고 싶으시면 다음의 유사 질문을 확인해 보세요:
- “알고리즘 시간 복잡도 이해하기” : 시간 복잡도에 대한 이해와 여러 알고리즘 사례를 다룹니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.