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

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

 

 

안녕하세요.

배열 강의 중 소수 구하기 (에라토스테네스의 체) 문제를 풀때 저는 계속 이중포문으로 진행하여 시간 초과 에러가 났습니다.

그래서 에라토스테네스의 체 라는 개념을 전혀 알지 못해서 일단 강의를 듣고 다시 풀어보자 라는 생각으로 강의를 진행했습니다.

 

에라토스테네스의 체 알고리즘을 이용하면 이중 for문이지만 빅오 표기법으로 O (N log logN) 이기 떄문에 시간초과가 나지않고 효과적으로 빠르게 코드가 실행되는것같습니다.

근데 제가 에라토스테네스의 체 에 해당하는 빅오표기법이 N log logN 이 나오도록 증명을 하고 싶은데,

구글링을 통해서 증명과정을 보려고해도 다들 그냥 N log logN 이라고 적어놓기만 했지 , 어떻게 해서 N log logN 이 되는지 자세히 설명한 글을 찾을 수 가 없습니다. ㅠㅠ

 

혹시 에라토스테네스의 체 의 빅오 계산이 어려운게 정상인가요?,,

그냥 다른 글들처럼 에라토스테네스의 체의 빅오 표기는 O(N log logN) 이 된다. 라고만 알고있어도 코딩테스트를 볼때 무리가 없을까요?

아니면 증명과정을 이해하는게 좋을까요?

혹시 이해해야 한다면 N log logN 이 되는 과정을 단순하게라도 설명해주신다면 감사하겠습니다 ㅠㅠ!