시간복잡도 계산 질문드립니다

조회수 1187회
  1. for(i = 1; i < n ; i *= 2) printf("Hello");

이 경우에 n/2 인가요 아니면 n/2 + 1일까요?

  1. for(i = 0; i < n ; i++) for(j = 1; j < n; j *=2) printf("hello"); 2번은 n2/2 맞나요?ㅠ

내일이 시험인데 아직도 헷갈려서 여쭤봅니다....

  • (•́ ✖ •̀)
    알 수 없는 사용자

1 답변

  • for(i = 1; i < n ; i *= 2) printf("Hello"); 이 경우에는 i가 2의 지수함수같이 증가합니다. 이 때에 시간복잡도는 2를 밑으로하는 log n 인 것 같습니다. 즉 log2(n) 입니다.

    for(i = 0; i < n ; i++) for(j = 1; j < n; j *=2) printf("hello") 같은 경우에는 일단 앞에서 n 이고 이후의 뒤에서 또 마찬가지로 2를 밑으로하는 logn 인 것 같습니다.

    죽 n *log2(n) 입니다.

    시간복잡도를 나타내는 방식은 계산하는 횟수를 식을 이용해서 나타내주면 됩니다...

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)