-
[학생] 컴공 자료구조 시간복잡도 문제 질문...2019.09.18 PM 07:43
sub 함수의 시간 복잡도가 일 때 다음 문장의 시간 복잡도는?
for(i=0;i<n;i*=2)sub();
위와 같은데...답이 O(nlogn) 입니다..
설명좀 해주실수있으실까요...ㅜㅠ
감사합니다.
댓글 : 5 개
- 오니언땅콩
- 2019/09/18 PM 08:05
음... 수행되는 횟수가 2^n < n 일 경우 때까지이니까, 양쪽에 log 취해서 계산하면 얼추 반복문 안의 함수가 logn번 수행될것 같아요
- foo@bar
- 2019/09/18 PM 08:26
for 문이 log n 번 실행되는것 같네요
- foo@bar
- 2019/09/18 PM 08:28
잠깐만... i=0 으로 시작하는것 맞나요?
- 이코ICO
- 2019/09/18 PM 08:36
n이 1 이상이면 무한 루프 ㄷㄷㄷ
- 날려진당
- 2019/09/18 PM 08:43
일단 i가 1부터 시작해야될것 같네요..
만약 i가 1부터라면 i는 1, 2, 4, 8... 2^k만큼 커지겠지요?
i는 2^k < n일때까지 커질거고 결국 k < logn이 되겠네용
만약 i가 1부터라면 i는 1, 2, 4, 8... 2^k만큼 커지겠지요?
i는 2^k < n일때까지 커질거고 결국 k < logn이 되겠네용