인프런 커뮤니티 질문&답변
작성한 질문수
자료구조 시간복잡도
작성
·
127
0
sub 함수의 시간 복잡도가 O(n)일 때 다음 코드의 시간 복잡도가 O(nlog2n)이라고 하는데 왜 그런지 알 수 있을까요? n이 홀수일 경우를 생각해보니 헷갈려서 질문드립니다.
코드는 아래와 같습니다.
for(int i = 1; i < n; i *= 2)
sub();답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
님의 질문에 대한 답변 드리겠습니다.
주어진 코드에서 for 루프는 i값을 1부터 시작해서 매번 2배씩 증가시키므로, i의 값은 1, 2, 4, 8, …과 같이 증가하게 됩니다. n이 어떤 값이든, 이 루프는 log2(n)번 반복됩니다. 왜냐하면 2를 log2(n)번 곱하면 n에 도달하기 때문입니다.
sub() 함수의 시간 복잡도가 O(n)으로 주어져 있는데, 이는 sub() 함수가 단독으로 실행될 때 n에 비례하여 시간이 걸린다는 의미입니다. 그러나 주어진 코드에서 sub() 함수는 for 루프 내에서 실행되므로, for 루프가 실행될 때마다 한 번씩 호출됩니다.
따라서 전체 코드의 시간 복잡도는 sub() 함수가 호출되는 횟수인 log2(n)에 sub() 함수의 시간 복잡도인 O(n)을 곱한 것인 O(nlog2(n))이 됩니다.
n이 홀수일 경우에도 for 루프의 종료 조건은 i < n이므로 i가 n을 초과하지 않는 마지막 값까지 반복됩니다. 이 경우에도 루프의 반복 횟수는 log2(n)에 의해 결정되므로 전체 시간 복잡도에 변함이 없습니다.
이해가 되셨길 바랍니다. 추가적인 질문이 있으시다면 문의해 주세요.