시간복잡도 문의

21.01.21 10:51 작성 조회수 145

시간복잡도가... 풀이와 같이 하면

j = 1일때 n번

j = 2일때 n/2번

j = 3일때 n/3번

…

j = n일때 n/n번

즉 total n * (1 + 1/2+1/3+…+1/n) 를 계산한 것이

시간복잡도가 되는것 맞나요 ? 아직 미흡해서 질문 남깁니다

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

9. 모두의 약수(제한시간 1초)

강의실 바로가기

답변 2

좋아요순

최신순

답변을 작성해보세요.

김태원

2021.01.21

안녕하세요^^

잘못계산하셨습니다.

시간복잡도는 N*((시그마 i=1~N) N/i )입니다. n * (n + n/2+n/3+…+n/n) 이 맞습니다.

나라심하 카루만치 책에서는 N*((시그마 i=1~N) N/i ) = O(NlogN) 이라 되어 있는 것 본적이 있습니다.

2021.01.21

아아 바깥for문을 깜빡했네요 !! 답해주셔서 감사합니다