루프형 시간 계산 시 초기화부분도 포함이 되나요?
조회수 501회
혼자 인강으로 자료구조수업을 듣는 군인입니다.
솔직히 적는 저 자신도 이런 걸 왜 물어보고 있나 하는 생각이 들지만
해답을 얻고자 질문을 드립니다.
for문이 다음과 같이 있다고 칩시다.
for( i = 1; i < n ; i ++ ) {
i = i + 1;
}
이럴 경우 저는 다음과 같이 생각했습니다.
| i | 반복차수 | n |
|---|---|---|
| 1 | 0 | 3 |
| 1+1 = 2 | 1 | 3 |
| 2+1 = 3 | 2 | 3 |
분명 여기서는 빅오가 O(n)입니다만,
여기서 횟수가 3이냐 2냐가 헷갈립니다.
과연
for문을 들어갈 때의i를 초기화하는 과정까지 포함하여 반복횟수가3인지,- 초기화 과정을 세지않고 반복문 횟수만 포함하여 총 반복횟수가
2인지
궁금합니다.
네 다들 말씀하시겠지만
메인은 시간복잡도이지, 반복횟수가 아니다. 결국 빅오를 구하여 함수의 효율성을 계산하는 과정일 뿐이다.
네. 그냥 이런 게 궁금한 사람일뿐입니다. 이게 그렇게 되는 건지, 왜 그렇게 되는건지 이해가 안 되면 못 넘어가는 사람이라....하하..
1 답변
-
죄송한 말씀인데 작성하신 코드는,
n=3일 경우, 루프를 2회 돌지도 않고 3회 돌지도 않고 딱 1번만 돕니다.- 초기식 부분이 실행됨.
i = 1 - 조건식 부분이 검증됨.
i < 3 == 1 < 3 == TRUE - 루프를 돌며 코드가 실행됨.
i = i + 1 == 1 + 1 == 2 - 다음 루프를 돌기 전 증감식 부분이 실행됨.
i = 2++ == 3 - 조건식 부분이 검증됨.
i < 3 == 3 < 3 == FALSE - 루프가 종료됨.
그건 그렇고
루프형 시간 계산 시 초기화부분도 포함이 되느냐?
하는 질문에만 답을 드리면, 아닐 겁니다.
증감식이나 조건 검증 부분이 엄청 무거운 연산을 돌린다면 또 모를까 단 1번 실행되는 초기화 부분이 루프 속도에 영향을 주는 일은 정말 거의 없습니다. (그리고 복잡도라는 개념은 기계가 그걸 연산하기가 힘들다 하는 것과는 거리가 있는 개념이죠. 이 부분은 이해하고 계시겠지만.) - 초기식 부분이 실행됨.
댓글 입력