소수 구하기 (에라토스테네스의 체) 빅오 표기법 질문 입니다.

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요. 배열 강의 중 소수 구하기 (에라토스테네스의 체) 문제를 풀때 저는 계속 이중포문으로 진행하여 시간 초과 에러가 났습니다. 그래서 에라토스테네스의 체 라는 개념을 전혀 알지 못해서 일단 강의를 듣고 다시 풀어보자 라는 생각으로 강의를 진행했습니다. 에라토스테네스의 체 알고리즘을 이용하면 이중 for문이지만 빅오 표기법으로 O (N log logN) 이기 떄문에 시간초과가 나지않고 효과적으로 빠르게 코드가 실행되는것같습니다. 근데 제가 에라토스테네스의 체 에 해당하는 빅오표기법이 N log logN 이 나오도록 증명을 하고 싶은데, 제 머리가 멍청해서인지, 왜 N log logN 이 나오는지 잘 모르겠습니다. 구글링을 통해서 증명과정을 보려고해도 다들 그냥 N log logN 이라고 적어놓기만 했지 , 어떻게 해서 N log logN 이 되는지 자세히 설명한 글을 찾을 수 가 없습니다. ㅠㅠ 혹시 에라토스테네스의 체 의 빅오 계산이 어려운게 정상인가요?,, 그냥 다른 글들처럼 에라토스테네스의 체의 빅오 표기는 O(N log logN) 이 된다. 라고만 알고있어도 코딩테스트를 볼때 무리가 없을까요? 아니면 증명과정을 이해하는게 좋을까요? 혹시 이해해야 한다면 N log logN 이 되는 과정을 단순하게라도 설명해주신다면 감사하겠습니다 ㅠㅠ!

김태원 · Answer

안녕하세요^^ 에라토스테네스 체 소수구하기의 시간복잡도가 정확하게 NlogN 이라고 수학적 증명을 할 수 는 없고 대략 NlogN에 가까운 성능을 가지고 있다 정도만 알면 됩니다.