시간 복잡도 관한 질문입니다.
조회수 2095회
int algorithm(int n){
int k = 0;
while(n>1) {
n=n/2;
k++;
}
return k;
}
시간복잡도 가 O(log n) 이 되는 이유가 궁금합니다.
-
(•́ ✖ •̀)
알 수 없는 사용자
1 답변
-
n=1인 경우
int k = 0 선언
n = 1 이므로 while문 조건 불만족
return 0
n=2인 경우
int k = 0 선언
n = 2 -> 1
k++ (k = 1)
n = 1 이므로 while문 조건 불만족
return 1
n=4인 경우
int k = 0 선언
n = 4 -> 2
k++ (k = 1)
n = 2 -> 1
k++ (k = 2)
n = 1 이므로 while문 조건 불만족
return 2
n=8인 경우
int k = 0 선언
n = 8 -> 4
k++ (k = 1)
n = 4 -> 2
k++ (k = 2)
n = 2 -> 1
k++ (k = 3)
n = 1 이므로 while문 조건 불만족
return 3
n=2a 인 경우
int k = 0 선언
n = 2a -> 2a-1
k++ (k = 1)
...생략...
n = 2 -> 1
k++ (k = a)
n = 1 이므로 while문 조건 불만족
return a
이 코드에서 k는 while루프가 진행되는 횟수와 동일합니다.
N이 2배로 증가할수록 코드 진행이 1번씩 늘어나고 있습니다. input 값이 N일때 while문은 a, 즉 log2N 번 돌게 되네요.
그리고 lnN이든, log2N, log10N 이든, Big-O로 표현하면 모두 logN이 된다고 합니다. (출처: 클라이드 C.)
추가로, 답변드릴려고 구글링 하다가 시간복잡도와 관련된 문서를 발견했습니다. 참고하세요~
댓글 입력