[학생] 컴공 자료구조 시간복잡도 문제 질문...

sub 함수의 시간 복잡도가 o(n)일 때 다음 문장의 시간 복잡도는?

   
      for(i=0;i<n;i*=2)sub();
   
   

위와 같은데...답이 O(nlogn) 입니다..

설명좀 해주실수있으실까요...ㅜㅠ 

감사합니다.

[오니언땅콩]

음... 수행되는 횟수가 2^n < n 일 경우 때까지이니까, 양쪽에 log 취해서 계산하면 얼추 반복문 안의 함수가 logn번 수행될것 같아요

[foo@bar]

for 문이 log n 번 실행되는것 같네요

[foo@bar]

잠깐만... i=0 으로 시작하는것 맞나요?

[이코ICO]

n이 1 이상이면 무한 루프 ㄷㄷㄷ

[날려진당]

일단 i가 1부터 시작해야될것 같네요..

만약 i가 1부터라면 i는 1, 2, 4, 8... 2^k만큼 커지겠지요?

i는 2^k < n일때까지 커질거고 결국 k < logn이 되겠네용