시간복잡도 계산 질문드립니다
조회수 1187회
- for(i = 1; i < n ; i *= 2) printf("Hello");
이 경우에 n/2 인가요 아니면 n/2 + 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) 입니다.
시간복잡도를 나타내는 방식은 계산하는 횟수를 식을 이용해서 나타내주면 됩니다...
댓글 입력